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();
 */
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成,瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明:文章內(nèi)容(如有圖片或視頻亦包括在內(nèi))由作者上傳并發(fā)布,文章內(nèi)容僅代表作者本人觀點(diǎn),簡書系信息發(fā)布平臺,僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 尤三歲閱讀 422評論 0 0
  • 天災(zāi)人禍都是無法避免的,昨天聽見朋友被訛被群毆,今日自己就撞邪了,走在大馬路上就被人家自行車事故給擠在中間,很明顯...
    瀟湘閣主閱讀 206評論 0 0
  • 正如Bits&Pieces所示,本章內(nèi)容比較雜而全。涵蓋了用詞、段落、寫作態(tài)度等多個方面。 在用詞方面: 其中最為...
    慢慢樹閱讀 282評論 0 2
  • 混沌也趕往神幻山。 純潔化成圣靈的模樣進(jìn)去。 “拜見和平之神”守衛(wèi)行禮。純潔直接進(jìn)去了。 “和平之神怎么提前來了,...
    白潔羽閱讀 457評論 0 0

友情鏈接更多精彩內(nèi)容