队列

队列（Queue）是一个数据集合，仅允许在列表的一端插入，在另一端删除。进行插入的一端称为“队尾”（rear），插入的动作称为入队；进行删除的一端称为“队头”（front），删除的动作称为出队。队列的性质是先进先出（FIFO，First-in-First-out）。下图为一个例子：

队列的实现方式：环形队列

设队列的最大长度为maxsize，队头指针为front，队尾指针为rear。上图中，队列最大长度为5，初始空队列front和rear都指向0。

• 当front == rear时，队为空，如图（a）
• 当(rear + 1) % maxsize == 0，队满。对于图（d1）的情况front == rear，无法判断到底是队空还是队满，因此需要牺牲一个存储单元，如图（d2）。
• 出队时队头指针前进1，front = (front + 1) % maxsize。
• 入队时队尾指针前进1，tear = (tear + 1) % maxsize。

上面的式子中，都有对maxsize的取余，因为比如当指针达到最大值5时，再加1就会超过5，此时取余可以重新进入队列循环。

栈

栈（stack）是一个数据集合，只能在一端进行插入和删除，其特点是后进先出（LIFO，lats-in-first-out）。栈的节本操作有进栈（push）、出栈（pop）、取栈顶（gettop）。其示意图如下所示：

对于python来说，使用列表即可实现栈。设列表为stack，其三个基本操作为：

• 入栈：stack.append()
• 出栈：stack.pop()
• 取栈顶：stack[-1]

例题

有效的括号

此题为leetcode第20题思路：使用栈，从给定的括号字符串第一个开始，依次往后，左半边括号入栈，遇到与之对应的右边吧括号出栈，直到最后若栈为空，则为有效表达，否则为无效表达。代码如下：

class Solution:
    def isValid(self, s: str) -> bool:
        map = {')':'(', ']':'[', '}':'{'}
        stack = []
        for char in s:
            # 如果是右括号
            if char in map:
                top = stack.pop() if stack else '#'
                if map[char] != top:
                    return False
            # 如果是左括号
            else:
                stack.append(char)
        return not stack

用队列实现栈

此题为leetcode第225题思路：使用两个队列可以实现栈，对于栈的push操作，可以由两个队列实现：

对于pop操作，直接从q1弹出即可

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.q2.append(x)
        while self.q1:
            self.q2.append(self.q1.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.q1.popleft()

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

    def empty(self) -> bool:
        '''
        Returns whether the stack is empty.
        '''
        return len(self.q1) == 0

用栈实现队列

此题为leetcode第232题思路：同样可以用两个栈实现队列，对于push操作：

class MyQueue:

    def __init__(self):
        '''
        Initialize your data structure here.
        '''
        self.s1, self.s2 = [], []

    def push(self, x: int) -> None:
        '''
        Push element x to the back of queue.
        '''
        while self.s1:
            self.s2.append(self.s1.pop())
        self.s1.append(x)
        while self.s2:
            self.s1.append(self.s2.pop())

    def pop(self) -> int:
        '''
        Removes the element from in front of queue and returns that element.
        '''
        return self.s1.pop()

    def peek(self) -> int:
        '''
        Get the front element.
        '''
        return self.s1[-1]

    def empty(self) -> bool:
        '''
        Returns whether the queue is empty.
        '''
        return len(self.s1) == 0