劍指Offer09.用兩個棧實現(xiàn)隊列

https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/solution/jian-zhi-offer09yong-liang-ge-zhan-shi-x-hybm/

難度：簡單

題目：

用兩個棧實現(xiàn)一個隊列。隊列的聲明如下，請實現(xiàn)它的兩個函數(shù) appendTail 和 deleteHead ，

分別完成在隊列尾部插入整數(shù)和在隊列頭部刪除整數(shù)的功能。(若隊列中沒有元素，deleteHead操作返回 -1 )

提示：

• 1 <= values <= 10000
• 最多會對 appendTail、deleteHead 進(jìn)行 10000 次調(diào)用

示例：

示例 1：

輸入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
輸出：[null,null,3,-1]
示例 2：

輸入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
輸出：[null,-1,null,null,5,2]

分析

首先掃盲隊列與棧的知識：

• 隊列：先進(jìn)先出
• 棧：后進(jìn)先出

那么，為什么要雙棧實現(xiàn)隊列呢？其實大家只要思考下：
我們準(zhǔn)備兩個棧add_stack和pop_stack：

1. 先把1,2,3先挨個加入add_stack棧
2. 下來依次將add_stack棧內(nèi)的數(shù)據(jù)出棧，同時將出棧的數(shù)據(jù)加入pop_stack棧中
3. 1、2執(zhí)行完成后，add_stack變成了空，pop_stack棧中存儲的數(shù)據(jù)成了[3,2,1]
4. 那么下次出棧時，直接將pop_stack的棧內(nèi)數(shù)據(jù)彈出，不就成了列隊的先進(jìn)先出！

關(guān)于什么時候執(zhí)行2步驟需要注意下：

1. 如果pop_stack棧中有數(shù)據(jù)，就直接return pop的數(shù)據(jù)
2. 如果pop_stack棧中沒有數(shù)據(jù)
   a. add_stack也沒有數(shù)據(jù)，return -1
   b. add_stack有數(shù)據(jù)，執(zhí)行上面步驟2，將add_stack數(shù)據(jù)加入pop_stack中
3. 返回pop_stack棧彈出的數(shù)據(jù)

解題：

class CQueue:
    def __init__(self):
        self.add_stack, self.pop_stack = [], []

    def appendTail(self, value: int) -> None:
        self.add_stack.append(value)

    def deleteHead(self) -> int:
        if self.pop_stack:
            return self.pop_stack.pop()
        if not self.add_stack:
            return -1
        while self.add_stack:
            self.pop_stack.append(self.add_stack.pop())
        return self.pop_stack.pop()

225.用隊列實現(xiàn)棧

https://leetcode-cn.com/problems/implement-stack-using-queues/solution/225yong-dui-lie-shi-xian-zhan-by-qingfen-igp1/

難度：簡單

題目：

請你僅使用兩個隊列實現(xiàn)一個后入先出（LIFO）的棧，并支持普通隊列的全部四種操作（push、top、pop 和 empty）。

實現(xiàn) MyStack 類：

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

注意：

• 你只能使用隊列的基本操作 —— 也就是push to back、peek/pop from front、size 和is empty這些操作。
• 你所使用的語言也許不支持隊列。你可以使用 list （列表）或者 deque（雙端隊列）來模擬一個隊列, 只要是標(biāo)準(zhǔn)的隊列操作即可。

示例：

輸入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
輸出：
[null, null, null, 2, 2, false]

解釋：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

分析

這道題的關(guān)鍵在于每次入隊時，如何保證入隊后新入隊的元素排在隊首，題目要求使用兩個隊列實現(xiàn)。

1. 首先我們創(chuàng)建兩個隊列，python操作為from collections import deque
2. 元素入隊時，將元素加入q1
3. 判斷q2是否存在元素，如果存在元素，則將元素依次出隊并加入q1的隊尾
4. 交換q1與q2
   至于出隊、查詢top、是否為空，都在q2上操作即可

解題：

from collections import deque


class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.q1 = deque()
        self.q2 = deque()

    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        self.q1.append(x)
        while self.q2:
            self.q1.append(self.q2.popleft())
        self.q1, self.q2 = self.q2, self.q1

    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        return self.q2.popleft()

    def top(self) -> int:
        """
        Get the top element.
        """
        return self.q2[0]

    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return not self.q2

歡迎關(guān)注我的公眾號: 清風(fēng)Python，帶你每日學(xué)習(xí)Python算法刷題的同時，了解更多python小知識。

我的個人博客：https://qingfengpython.cn

力扣解題合集：https://github.com/BreezePython/AlgorithmMarkdown