用棧實現隊列 - 用隊列實現棧

棧和隊列

棧和隊列都是一種數據結構，它們的作用都是存儲。

每種數據結構都有着其對應的特性。隊列的特性是先進先出，而棧的特性是先進後出：

只有滿足了它們的以上特性，一個數據結構才能被稱爲棧或者隊列。

接下來我們看一下這兩道經典的數據結構設計題：

用棧實現隊列

要用棧實現隊列，就得實現隊列的以下 API：

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

我們要讓設計的隊列滿足以上 API 的使用。

隊列有隊列頭部和隊列尾部。所以我們可以用兩個棧，通過棧的特性讓它們相互配合從而實現一個隊列：

    Stack<Integer> stackPush;  //一個棧用來負責push元素
    Stack<Integer> stackPop; //一個棧用來負責將元素pop掉

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

push():

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

所以這裏我們可以直接調用棧的 push()，然後把元素打入 stachPush 這個棧就好了：

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

此時，元素 1 就在 stachPush 這個棧的底部：

pop():

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

有了剛纔 push() 的經驗，pop() 依然可以按照 push() 剛纔經驗，就是當 stackPop 爲空的時候，按順序把 stackPush 裏面的元素一個一個 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 就是返回隊列的頭個元素：

pop() 和 peek() 的區別是什麼呢？就是 pop() 返回隊列頭個元素並且要刪除，但是 peek() 返回卻不刪除呀。

所以，和 pop() 的思路一樣，只需要在最後返回的時候把 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()：

判斷隊列是否爲空，爲空就返回 true，不爲空就返回 false。

所以我們也可以直接判斷兩個棧是否同時爲空。只要同時爲空就返回 true，不同時爲空就返回 false：

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

可以看出，用棧實現隊列思路還是比較簡單的。主要利用的是兩個棧的相互配合。其核心思路就是一個數據從一個棧的隊尾移動到另一個棧，就處於隊頭的位置。

那麼來說一下時間複雜度，當隊列爲空的時候 pop() 和 peek() 都要通過 while 循環把元素從 stackPush 移動到 stackPop，所以複雜度是 O(n)。

用隊列實現棧

先看看棧的 API：

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

和隊列的 API 一樣。只不過這一次我們是要模擬由隊列實現棧。

如果說用棧實現隊列是一種相互配合的方式的話，那麼由隊列實現棧就不需要了。我們可以使用 ArrayDeque() 來實現隊列。

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

push(int x)：

根據棧的特性，第一個入棧的元素會處於棧底部。所以在使用隊列模擬棧的時候，可以先把元素入隊列，然後再一個一個拿出來，最後再入一次隊列，這樣子原本處於隊列頭的元素就到了隊列尾部，相當於棧頭：

    // 入棧時，將新元素x進入隊列後，將新元素x之前的所有元素重新入隊，此時元素x處於隊頭
    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():

由於出棧的操作是和出隊列的操作是相同的，當我們把元素從隊列頭變到隊列尾部後，就直接 poll() 出來即可：

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

top() ：

獲取棧頭部元素，就相當於隊列的 peek():

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

empty():

返回隊列是否爲空，都是通用的：

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

相比於用棧實現隊列，用隊列實現棧就非常簡單。核心思想就是將隊列的元素先拿出來再放進去從而滿足先進後出的特性。

那麼它們的時間複雜度是多少呢？其它操作都是 O(1)。只有 pop() 操作需要通過循環把元素從隊列拿出來再放進去，所以時間複雜度是 O(n)。

以上就是用棧實現隊列 & 用隊列實現棧的思路。主要是用來考察棧和隊列的特性。

我是 fancy，我們下次見！

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/-sjGDJe3xHmEXLMbLYk9QQ

棧和隊列

用棧實現隊列

用隊列實現棧

猜你喜歡