232.用棧實(shí)現(xiàn)隊(duì)列

題目描述：
push(x) -- 將一個(gè)元素放入隊(duì)列的尾部。
pop() -- 從隊(duì)列首部移除元素。
peek() -- 返回隊(duì)列首部的元素。
empty() -- 返回隊(duì)列是否為空。

解題思路：

運(yùn)用兩個(gè)棧，輸入棧和輸出棧來實(shí)現(xiàn)隊(duì)列的操作

class MyQueue {

    Stack<Integer> stackIn;
    Stack<Integer> stackOut;


    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();

    }
    
    public void push(int x) {
        stackIn.push(x);
    }
    
    public int pop() {
        dumpstackIn();
        return stackOut.pop();

    }
    
    public int peek() {
        dumpstackIn();
        return stackOut.peek();

    }
    
    public boolean empty() {
        return stackOut.isEmpty() && stackOut.isEmpty();

    }
    
        //復(fù)用函數(shù)dumpstackIn來完成pop和peek的動(dòng)作
        //因?yàn)閜op和peek都是要將輸入棧的數(shù)據(jù)導(dǎo)入輸出棧
    private void dumpstackIn(){
        if (stackOut.isEmpty()){
            while (!stackIn.isEmpty()){
                stackOut.push(stackIn.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();
 */

225. 用隊(duì)列實(shí)現(xiàn)棧

題目描述：
使用隊(duì)列實(shí)現(xiàn)棧的下列操作：

push(x) -- 元素 x 入棧
pop() -- 移除棧頂元素
top() -- 獲取棧頂元素
empty() -- 返回棧是否為空

注意:
你只能使用隊(duì)列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 這些操作是合法的。
你所使用的語言也許不支持隊(duì)列。 你可以使用 list 或者 deque（雙端隊(duì)列）來模擬一個(gè)隊(duì)列 , 只要是標(biāo)準(zhǔn)的隊(duì)列操作即可。
你可以假設(shè)所有操作都是有效的（例如, 對(duì)一個(gè)空的棧不會(huì)調(diào)用 pop 或者 top 操作）。

理論知識(shí)：

隊(duì)列的操作：
·添加元素：add() 拋異常;offer(); 返回null
·返回第一個(gè)元素：element() 拋異常; peek() null;
·刪除第一個(gè)元素：remove() 拋異常; poll() null;
·判斷隊(duì)列是否為空：isEmpty();
棧的操作：
·把項(xiàng)壓入棧頂：push()
·查看棧頂元素：不刪除：peek();
·移除棧頂元素：pop();
·判斷棧是否為空：Empty();

解題方法：?jiǎn)蜗蜿?duì)列

解題思路：
利用兩個(gè)隊(duì)列來模擬棧，隊(duì)列1為保持跟棧一樣順序的隊(duì)列，隊(duì)列2則是輔助操作；
1.push()：新增的元素相放到隊(duì)列2中，判斷隊(duì)列1狀態(tài)：
如果隊(duì)列1為空，則直接交換兩隊(duì)元素，隊(duì)列2始終保持為空；
如果隊(duì)列1不為空，則先將隊(duì)列1的元素依次放入隊(duì)列2中，再交換q1和q2
2.pop();top();Empty()操作都只需對(duì)q1操作即可

class MyStack {
    Queue<Integer> q1;
    Queue<Integer> q2;

    public MyStack() {
        q1 = new LinkedList<>(); //q1用來保持跟站內(nèi)一樣順序的元素
        q2 = new LinkedList<>(); //q2用來做輔助操作

    }
    
    public void push(int x) {
        q2.offer(x);
        //判斷q1是否為空，若為空直接交換q1和q2元素；若不為空，就將q1的元素依次放入q2
        while (!q1.isEmpty()) {
            q2.offer(q1.poll());
        }
        //交換q1和q2的元素，保存在q1中
        Queue<Integer> temp = new LinkedList<>();
        temp = q1;
        q1 = q2;
        q2 = temp;

    }
    
    public int pop() {
        return q1.poll();

    }
    
    public int top() {
        return q1.peek();

    }
    
    public boolean empty() {
        return q1.isEmpty();

    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */