本文最后更新于:2 个月前

一、队列

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

Sample

图1:队列

队列的实现方式:环形队列
在这里插入图片描述
设队列的最大长度为maxsize,队头指针为front,队尾指针为rear。上图中,队列最大长度为5,初始空队列frontrear都指向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)。其示意图如下所示:

Sample

图1:队列

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

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

三、例题

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

2、用队列实现栈

此题为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

3、用栈实现队列

此题为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