首页 > 试题广场 >

用两个栈实现一个队列的功能?要求给出算法和思路!

[问答题]

用两个栈实现一个队列的功能?要求给出算法和思路!
设2个栈为A,B, 一开始均为空.

入队:
将新元素push入栈A;

出队:
(1)判断栈B是否为空;
(2)如果不为空,则将栈A中所有元素依次pop出并push到栈B;
(3)将栈B的栈顶元素pop出;


这样实现的队列入队和出队的平摊复杂度都还是O(1), 比上面的几种方法要好。

推荐
/*
声明两个栈 stackPush,用来保存入栈的数据,stackPop用来保存出站的数据。
入栈时,只需向stackPush添加数据。当stackPop栈中的数据为空时,
就一次性把stackPush中的数据导入到stackPop中,避免二次添加时,出来的数据不一致性的问题。

*/
import java.util.Stack;

public class TwoStacksImplementQueue {

	public static class TwoStacksQueue {
		public Stack<Integer> stackPush;
		public Stack<Integer> stackPop;

		public TwoStacksQueue() {
			stackPush = new Stack<Integer>();
			stackPop = new Stack<Integer>();
		}

		public void push(int value) {
			stackPush.push(value); }

		public int poll() {
			if (stackPop.empty() && stackPush.empty()) {
				throw new RuntimeException("Queue is empty!");
			} else if (stackPop.empty()) {
				while (!stackPush.empty()) {
					stackPop.push(stackPush.pop());
				}
			}
			return stackPop.pop();
		}

		public int peek() {
			if (stackPop.empty() && stackPush.empty()) {
				throw new RuntimeException("Queue is empty!");
			} else if (stackPop.empty()) {
				while (!stackPush.empty()) {
					stackPop.push(stackPush.pop());
				}
			}
			return stackPop.peek();
		}
	}
}

编辑于 2016-11-21 12:00:30 回复(0)
import java.util.Stack;
 
public class AlgorithmTest20190818 {
 
    /**
     * 用两个栈实现队列(先进先出)
     * 实现思路:
     * (1)stack1作为队尾栈,元素每次进队列都放到队尾栈的栈顶。
     * (2)stack2作为队头栈,元素每次出队列都从队头栈出队。
     * (3)当队头栈为空时,将队尾栈的元素循环出栈放到队头栈。队尾栈栈底的元素(先排队的元素)就会变成队头栈的栈顶元素,可以优先出栈(即出队)。
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        for (int i = 0; i < arr.length; i++) {
            push(arr[i]);
        }
        System.out.println(pop());
        System.out.println(pop());
        push(4);
        System.out.println(pop());
        push(5);
        System.out.println(pop());
        System.out.println(pop());
    }
 
    /**
     * 队尾栈
     */
    static Stack<Integer> stack1 = new Stack<Integer>();
 
    /**
     * 队头栈
     */
    static Stack<Integer> stack2 = new Stack<Integer>();
 
    public static void push(int node) {
        stack1.push(node);
    }
 
    public static int pop() {
        if(stack1.empty() && stack2.empty()){
            throw new RuntimeException("队列为空!");
        }
        if (stack2.size() == 0) {
            // 将队尾栈的元素全部放到队头栈
            while (!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
 
}

发表于 2020-03-03 08:31:17 回复(0)
import java.util.Stack;

public class QueeByStack {

	/**
	 * @param args
	 * @throws Exception 
	 */
	public static void main(String[] args) throws Exception {
		
		QueeByStack qbs = new QueeByStack();
		qbs.put(1);
		qbs.put(2);
		qbs.put(3);
		qbs.put(4);
	
		qbs.out();
		qbs.out();
		qbs.put(5);
		qbs.put(6);
		qbs.put(7);
		qbs.out();
		
	}
	
	private Stack<Integer> stack1 =new Stack<Integer>();
	private Stack<Integer> stack2 =new Stack<Integer>();
	

	public void put(Integer t){
		stack1.push(t);
		//System.out.println(t);
	}
	
	public void out() throws Exception{
		if(stack2.isEmpty()){
			while(!stack1.isEmpty()){
				stack2.push(stack1.pop());
			}
		}
		if(stack2.isEmpty()){
			throw new Exception("队列为空,无法删除");
		}
		//return stack2.pop();
		
		System.out.println(stack2.pop());
	}
}


发表于 2016-03-10 15:43:03 回复(0)