用两个栈模拟队列(java实现)

要用两个栈实现队列,首先要明确栈和队列的定义:

栈:只能在表尾进行插入删除的线性表

队列:只能在一端进行删除,另一端进行插入的线性表

在明确栈和队列的定义后,我们现在来讨论它的具体实现过程:

对于栈而言,其遵循后进先出的原则(LIFO),后进的元素反而会最先弹出;而队列遵循的是先进先出的原则(FIFO)。

对于队列的入队,由于要用两个栈来替代队,而栈的存取数据只有压栈操作,故而队列的入队操作等价于栈的入栈操作。

对于队列的出队,,,用两个栈的模拟就有点,,,嗯。。。意思了^_^,,,要出队,首先队列中要有元素,也就是说,栈中已经有元素了,如下图:

用两个栈模拟队列(java实现)_第1张图片

对于一个有元素的栈,其弹栈就是把栈顶的元素删除,而栈顶的元素刚好是最近的入栈的元素,故而用简单的栈的弹栈来模拟队列的出队是不现实的。。。此时,,,看上图,是不是发现还有一个栈还在孤零零的“空着肚子”站在那里,然后在联立问题:“用两个栈来模拟队列”,那这个空着的栈,根据老夫多年的实战经验,它肯定不是只是个“花瓶”!那它能用来干什么呢?假如我们把栈1中的元素依次弹出来,然后在把它们压入“饿着肚子”的栈2,此时,情况是这样的:

用两个栈模拟队列(java实现)_第2张图片

哎,,,这个时候,如果再把栈2中的元素来弹出来,刚好是反着方向将元素删除哦,刚好满足队列的出队原则哦~那这样的话,用两个栈完全可以实现队列的出队操作,perfect!

注:这里我们假设,入栈的元素数量不会超过栈的内存空间

下面我们看一下代码:

import java.util.*;

public class Solution1314{
	Stack stack1 = new Stack();
    Stack stack2 = new Stack();
    
    public void push(int node) {
         stack1.push(node);
    }
    
    public int pop() {
		if(stack2.isEmpty()){
			Enumeration items=stack1.elements();
		    int num=0;
		    while(items.hasMoreElements()){
				items.nextElement();
			    num++;
			}
		    for(int i=num;i>0;i--){
				int temp=stack1.peek();
			    stack2.push(temp);
				stack1.pop();
			}
		}
		int outteam=stack2.pop();
		return outteam;
    }
}

你可能感兴趣的