棧和隊(duì)列

棧和隊(duì)列都是一種數(shù)據(jù)結(jié)構(gòu)，它們的作用都是存儲(chǔ)。

每種數(shù)據(jù)結(jié)構(gòu)都有著其對(duì)應(yīng)的特性。隊(duì)列的特性是先進(jìn)先出，而棧的特性是先進(jìn)后出：

只有滿足了它們的以上特性，一個(gè)數(shù)據(jù)結(jié)構(gòu)才能被稱為棧或者隊(duì)列。

接下來(lái)我們看一下這兩道經(jīng)典的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)題：

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

要用棧實(shí)現(xiàn)隊(duì)列，就得實(shí)現(xiàn)隊(duì)列的以下API：

void push(int x) // 將元素添加到隊(duì)列的尾處
int pop() //刪除隊(duì)列的頭部元素并且返回
int peek() //返回隊(duì)列的頭個(gè)元素
boolean empty() //判斷隊(duì)列是否為空

我們要讓設(shè)計(jì)的隊(duì)列滿足以上API的使用。

隊(duì)列有隊(duì)列頭部和隊(duì)列尾部。所以我們可以用兩個(gè)棧，通過(guò)棧的特性讓它們相互配合從而實(shí)現(xiàn)一個(gè)隊(duì)列：

    Stack<Integer> stackPush;  //一個(gè)棧用來(lái)負(fù)責(zé)push元素
    Stack<Integer> stackPop; //一個(gè)棧用來(lái)負(fù)責(zé)將元素pop掉

    //初始化
    public MyQueue() {
        stackPush = new Stack<Integer>();
        stackPop = new Stack<Integer>();
    }

push():

push()要做的，就是將一個(gè)元素添加到隊(duì)列的尾處。

所以這里我們可以直接調(diào)用棧的push()，然后把元素打入stachPush這個(gè)棧就好了：

    public void push(int x) {
        stackPush.push(x);
    }

此時(shí)，元素1就在stachPush這個(gè)棧的底部：

pop():

pop()就是刪除隊(duì)列的頭部元素并且返回。

有了剛才push()的經(jīng)驗(yàn)，pop()依然可以按照push()剛才經(jīng)驗(yàn)，就是當(dāng)stackPop為空的時(shí)候，按順序把stackPush里面的元素一個(gè)一個(gè)pop()掉，并且返回給stackPop：

然后再將stackPop()里面的元素pop()返回：

    public int pop() {
        if (stackPop.isEmpty() && stackPush.isEmpty()) {
            throw new RuntimeException("Queue is empty.");
        } else {
            if (stackPop.isEmpty()) {
                while (!stackPush.isEmpty()) {
                    stackPop.push(stackPush.pop());
                }
            }
        }
        return stackPop.pop();
    }

peek()：

peek就是返回隊(duì)列的頭個(gè)元素：

pop()和peek()的區(qū)別是什么呢？就是pop()返回隊(duì)列頭個(gè)元素并且要?jiǎng)h除，但是peek()返回卻不刪除呀。

所以，和pop()的思路一樣，只需要在最后返回的時(shí)候把stackPop.pop()換成stackPop.peek()就完事了。

    public int peek() {
        if (stackPush.isEmpty() && stackPop.isEmpty()) {
            throw new RuntimeException("Queue is empyt.");
        } else {
            if (stackPop.isEmpty()) {
                while (!stackPush.isEmpty()) {
                    stackPop.push(stackPush.pop());
                }
            }
        }
        return stackPop.peek();
    }

empty()：

判斷隊(duì)列是否為空，為空就返回true，不為空就返回false。

所以我們也可以直接判斷兩個(gè)棧是否同時(shí)為空。只要同時(shí)為空就返回true，不同時(shí)為空就返回false：

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

可以看出，用棧實(shí)現(xiàn)隊(duì)列思路還是比較簡(jiǎn)單的。主要利用的是兩個(gè)棧的相互配合。其核心思路就是一個(gè)數(shù)據(jù)從一個(gè)棧的隊(duì)尾移動(dòng)到另一個(gè)棧，就處于隊(duì)頭的位置。

那么來(lái)說(shuō)一下時(shí)間復(fù)雜度，當(dāng)隊(duì)列為空的時(shí)候pop()和peek()都要通過(guò)while循環(huán)把元素從stackPush移動(dòng)到stackPop，所以復(fù)雜度是O(n)。

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

先看看棧的API：

void push(int x) //將元素壓入棧頂
int pop() //移除并返回棧頂元素
int top() //返回棧頂元素
boolean empty() //如果棧是空的，返回 true ；否則，返回 false 。

和隊(duì)列的API一樣。只不過(guò)這一次我們是要模擬由隊(duì)列實(shí)現(xiàn)棧。

如果說(shuō)用棧實(shí)現(xiàn)隊(duì)列是一種相互配合的方式的話，那么由隊(duì)列實(shí)現(xiàn)棧就不需要了。我們可以使用ArrayDeque()來(lái)實(shí)現(xiàn)隊(duì)列。

    Queue<Integer> queue;
    // 使用ArrayDeque作為隊(duì)列
    public MyStack() {
        queue = new ArrayDeque<>();
    }

push(int x)：

根據(jù)棧的特性，第一個(gè)入棧的元素會(huì)處于棧底部。所以在使用隊(duì)列模擬棧的時(shí)候，可以先把元素入隊(duì)列，然后再一個(gè)一個(gè)拿出來(lái)，最后再入一次隊(duì)列，這樣子原本處于隊(duì)列頭的元素就到了隊(duì)列尾部，相當(dāng)于棧頭：

    // 入棧時(shí)，將新元素x進(jìn)入隊(duì)列后，將新元素x之前的所有元素重新入隊(duì)，此時(shí)元素x處于隊(duì)頭
    public void push(int x) {
        queue.offer(x);
        int size = queue.size();
        for (int i = 0; i < size - 1; i++) {
            queue.offer(queue.poll());
        }
    }

pop():

由于出棧的操作是和出隊(duì)列的操作是相同的，當(dāng)我們把元素從隊(duì)列頭變到隊(duì)列尾部后，就直接poll()出來(lái)即可：

    public int pop() {
        if (queue.isEmpty()) {
            throw new RuntimeException("EMPTY STACK");
        }
        return queue.poll();
    }

top() ：

獲取棧頭部元素，就相當(dāng)于隊(duì)列的peek():

    public int top() {
        if (queue.isEmpty()) {
            throw new RuntimeException("EMPTY STACK");
        }
        return queue.peek();
    }

empty():

返回隊(duì)列是否為空，都是通用的：

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

相比于用棧實(shí)現(xiàn)隊(duì)列，用隊(duì)列實(shí)現(xiàn)棧就非常簡(jiǎn)單。核心思想就是將隊(duì)列的元素先拿出來(lái)再放進(jìn)去從而滿足先進(jìn)后出的特性。

那么它們的時(shí)間復(fù)雜度是多少呢？其它操作都是O(1)。只有pop()操作需要通過(guò)循環(huán)把元素從隊(duì)列拿出來(lái)再放進(jìn)去，所以時(shí)間復(fù)雜度是O(n)。

以上就是用棧實(shí)現(xiàn)隊(duì)列 & 用隊(duì)列實(shí)現(xiàn)棧的思路。主要是用來(lái)考察棧和隊(duì)列的特性。