Implement Queue using two stack

Since the major difference between a queue and a stack is the order(FIF vs LIFO), we know we need to modify peek() and pop() to go in reverse order. We can use our second stack to reverse the order of the elements (by poping s2 and pushing the elements on to s1).

public class MyQueue {
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    /** Initialize your data structure here. */
    public MyQueue() {
        stack1 = new Stack<Integer>();
        stack2 = new Stack<Integer>();
    }
    
    public int size() {
         return stack1.size() + stack2.size();
    }
    /** Push element x to the back of queue. */
    public void push(int x) {
        stack2.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if(stack1.isEmpty() == true) {
            stack2ToStack1();
        }
        if (stack1.isEmpty() != true) {
            return stack1.pop();
        } else {
            return -1;
        }
    }
    
    /** Get the front element. */
    public int peek() {
        if(stack1.isEmpty() == true) {
            stack2ToStack1();
        }
        if (stack1.isEmpty() != true) {
            return stack1.peek();
        } else {
            return -1;
        }
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        if(stack1.isEmpty() == true) {
            stack2ToStack1();
        }
        
        return stack1.isEmpty();
    }
    
    private void stack2ToStack1() {
        while (!stack2.empty()) {
            stack1.push(stack2.pop());
        }
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 尤三岁阅读 2,972评论 0 0
  • 天灾人祸都是无法避免的,昨天听见朋友被讹被群殴,今日自己就撞邪了,走在大马路上就被人家自行车事故给挤在中间,很明显...
    潇湘阁主阅读 1,459评论 0 0
  • 正如Bits&Pieces所示,本章内容比较杂而全。涵盖了用词、段落、写作态度等多个方面。 在用词方面: 其中最为...
    慢慢树阅读 1,688评论 0 2
  • 混沌也赶往神幻山。 纯洁化成圣灵的模样进去。 “拜见和平之神”守卫行礼。纯洁直接进去了。 “和平之神怎么提前来了,...
    白洁羽阅读 3,077评论 0 0

友情链接更多精彩内容