利用栈Stack实现队列(Queue)

谁借莪１个温暖的怀抱￠ 2022-08-02 07:30 217阅读 0赞

实现说明：

入队时，将元素压入s1;

出队时，判断s2是否为空，如不为空，则直接弹出顶元素；如为空，则将s1的元素逐个“倒入”s2，把最后一个元素弹出并出队;

这个思路，避免了反复“倒”栈，仅在需要时才“倒”一次。

package com.knowledgeStudy.threadLocal;
    
    import java.util.Stack;
    
    public class MyQueue {
    
        Stack<Object> s1 = new Stack<Object>();//入栈
    
        Stack<Object> s2 = new Stack<Object>();//出栈
    
        // Push element x to the back of queue.
        public void push(Object x) {
            s1.push(x);
        }
    
        // Removes the element from in front of queue.  
        public void pop() {
            if (!s2.isEmpty()) {
                s2.pop();
            } else {
                while (!s1.isEmpty()) {
                    s2.push(s1.pop());
                }
                s2.pop();
            }
        }
    
        // Get the front element.  
        public Object peek() {
            if (!s2.isEmpty()) {
                return s2.peek();
            } else {
                while (!s1.isEmpty()) {
                    s2.push(s1.pop());
                }
                return s2.peek();
            }
        }
    
        // Return whether the queue is empty.
        public boolean empty() {
            return s1.empty() && s2.empty();
        }
       //测试
        public static void main(String[] args) {
            MyQueue queue = new MyQueue();
            queue.push(1);
            queue.pop();
            System.out.println(queue.empty());
        }
    }