一、栈实现队列原理分析
栈：允许在一端进行增删操作的特殊线性表，遵循先进后出的规则。
队列：允许分别在两端进行增删操作的特殊线性表，遵循先进先出的规则。
如果使用栈来实现一个队列的功能呢？
1.1、因为队列可以实现分别在两端进行增删操作，所以需要一个栈来模拟入队操作，另外一个栈来模拟出队操作。
栈模拟队列操作.png
1.2、众所周知，栈遵循的原则和队列是相反的，那么如果使用两个栈来实现队列操作呢？按照如下步骤：
1：队列的入队操作，就正常往栈A插入数据就好。
2：队列如果发生出队操作，这时候需要判断栈B是否为空，如果不为空则直接pop这个元素，即队列出队的元素。如果为空，则将栈A的元素依次从栈顶pop出去，然后push进栈B。
3：栈A弹出，在次压栈进栈B，可以想象，元素的次序刚好颠倒。
让1元素先入队列：
image.png
让2元素入队列：
image.png
让3元素入队列：
image.png
这时候需要出队列，按照队列的规则应该是1元素出队列，这时候需要参考刚才分析的步骤2操作，将栈A的元素弹栈在压栈进B：
image.png
然后在让1出队列：
image.png
然后在让2出队列：
image.png
如果这时候有新元素进队列，比如说元素4：
image.png
然后在执行一次出队操作：
image.png
这时候栈B已经空了，如果在执行出队操作，还是按照步骤2分析的操作：
image.png
二、实现代码-java
代码当中使用的栈是自定义，代码可以参考栈的原理与实现
public class StackQueue {
/**
* 使用栈来实现队列，栈的特性是在一端进行增删操作，遵循先进后出的原则。
* 队列允许在两端分别进行增删操作，遵循先进先出的原则，所以在用栈实现
* 队列的前提下，需要用到一个辅助栈。
*/
MyArrayStack stackPop;
MyArrayStack stackPush;
public StackQueue(){
stackPop = new MyArrayStack(10); //辅助栈
stackPush = new MyArrayStack(10); //真正插入数据的栈
}
public void queuePush(Object elem){
//往队列里面插入一个值
stackPush.push(elem);
}
public Object queuePoll(){
if (stackPush.top == -1 && stackPop.top == -1){
return null;
}
return pushToStackPop();
}
public void queuePeek(){
if (stackPush.top == -1 && stackPop.top == -1){
return;
}
peekToStackPop();
}
private Object pushToStackPop() {
if (stackPop.top == -1){
while(stackPush.top > -1){
stackPop.push(stackPush.pop());
}
}
return stackPop.pop();
}
private Object peekToStackPop() {
if (stackPop.top == -1){
while(stackPush.top != -1){
stackPop.push(stackPush.pop());
}
}
return stackPop.GetTop();
}
public static void main(String[] args) {
StackQueue stackQueue = new StackQueue();
stackQueue.queuePush("zhangsan");
stackQueue.queuePush("lisi");
System.out.println(stackQueue.queuePoll());
System.out.println(stackQueue.queuePoll());
}
}
三、时间复杂度分析
其实用栈实现队列，主要有两种操作：
1、入队操作，入队对应栈来说，其实就是普通的压栈操作，时间复杂度是O(1)。
2、出队操作，出队操作对应栈来说，这里可能存在两种情况，第一种情况就是栈B（辅助栈）非空，直接弹栈就好，这时候时间复杂度是O(1)，如果栈B为空，这时候需要将栈A的全部元素都压栈进B，这时候的时间复杂度是O(n)。从这里可以看出，当不经常出队，或者发生出队以后，后续很少发生栈迁移的情况，均衡时间复杂度可以认为是O(1).
网友评论