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

怎么用棧實(shí)現(xiàn)隊(duì)列？
隊(duì)列的特點(diǎn)是：先進(jìn)先出
可以用兩個棧實(shí)現(xiàn)，將棧A的棧頂元素出棧，再壓入棧B。循壞該動作，直到A棧為空。這時棧B的棧頂元素就是隊(duì)首元素。棧B中元素依次出棧即出隊(duì)列。

import java.util.ArrayList;

public class MyQueue {
    private ArrayList<Integer> in;
    private ArrayList<Integer> out;

    public MyQueue() {
        in = new ArrayList<Integer>();
        out = new ArrayList<Integer>();
    }

    public void push(int x) {
        in.add(x);
    }

    public int pop() {
        if (out.isEmpty()) {
            int size = in.size();
            for (int i = 0; i < size; i++) {
                int v = in.remove(in.size() - 1);
                out.add(v);
            }
        }

        return out.remove(out.size() - 1);
    }

    public int peek() {
        if (out.isEmpty()) {
            int size = in.size();
            for (int i = 0; i < size; i++) {
                int v = in.remove(in.size() - 1);
                out.add(v);
            }
        }

        return out.get(out.size() - 1);
    }

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

怎么用隊(duì)列實(shí)現(xiàn)棧？
棧的特點(diǎn)是：先進(jìn)后出
調(diào)用隊(duì)列的方法，取出隊(duì)首元素尾插在隊(duì)尾，如此循壞等價于逆序了隊(duì)列。這時候的隊(duì)首即是棧頂。

import java.util.LinkedList;

class MyStack {
    private LinkedList<Integer> queue;

    /** Initialize your data structure here. */
    public MyStack() {
        queue = new LinkedList<>();
    }

    /** Push element x onto stack. */
    public void push(int x) {
        queue.addLast(x);
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        int size = queue.size();
        for (int i = 0; i < size - 1; i++) {
            int v = queue.pollFirst();
            queue.addLast(v);
        }

        return queue.pollFirst();
    }

    /** Get the top element. */
    public int top() {
        int size = queue.size();
        for (int i = 0; i < size - 1; i++) {
            int v = queue.pollFirst();
            queue.addLast(v);
        }

        int v = queue.pollFirst();
        queue.addLast(v);
        return v;
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue.isEmpty();
    }
}