第二章栈与队列（Python实现版）

一、栈Stack
- 1.1 栈的定义
- 1.2 栈的实现
- 1.3 栈的应用
  - 1.3.1 撤销操作
  - 1.3.2 有效的括号（20）
  - 1.3.3 四则运算表达式求值
  - 1.3.4 ⭐⭐程序员代码面试指南-设计一个有getMin功能的栈
二、队列Queue
- 2.1 队列的定义
- 2.2 队列的实现
- 2.3 数组队列的问题
- 2.4 循环队列
  - 2.4.1 循环队列定义
  - 2.4.2 循环队列实现
- 2.5 双端队列
  - 2.5.1 双端队列定义
  - 2.5.2 双端队列实现
- 2.6 队列的应用
  - 2.6.1 回文词检测
  - 2.6.2 用栈实现队列（232）
    - 解法一：在一个栈中维持所有元素的出队顺序
    - 解法二：一个栈入，一个栈出
  - 2.6.3 滑动窗口最大值（239）

在这里插入图片描述

一、栈Stack

1.1 栈的定义

官方定义：栈是限定仅在表尾进行插入和删除操作的线性表；

解释：栈也是一种线性结构，相比数组，栈对应的操作是数组的子集，只能从一端添加元素，也只能从一端取出元素。

把允许删除和插入的一端称为栈顶（top），另一端称为栈底（bottom）。

栈是一种后进先出的数据结构：Last In First Out (LIFO)

在这里插入图片描述

思考：最先进栈的元素，是不是就只能是最后出栈？
不一定，但是依然要满足只能从栈顶进出。

1.2 栈的实现

Stack() 创建一个新的空栈
push(elem) 添加一个新的元素elem到栈顶
pop() 弹出栈顶元素
peek() 返回栈顶元素
is_empty() 判断栈是否为空
size() 返回栈的元素个数

class Stack(object):"""栈"""def __init__(self):self.items = []def is_empty(self):'''判断栈是否为空'''return self.items == []def push(self, item):'''加入元素'''self.items.append(item)def pop(self):'''弹出元素'''return self.items.pop()def peek(self):'''返回栈顶元素'''return self.items[len(self.items) - 1]def size(self):'''返回栈的大小'''return len(self.items)

if __name__ == "__main__":stack = Stack()stack.push("Hello")stack.push("My")stack.push("Friend")print(stack.items)print(stack.size())print(stack.peek())print(stack.pop())print(stack.items)print(stack.pop())print(stack.pop())print(stack.items)

输出如下：

['Hello', 'My', 'Friend']
3
Friend
Friend
['Hello', 'My']
My
Hello
[]

用数组直接实现功能不就行了吗？干嘛要引入栈这样的数据结构呢？

栈的引入简化了程序设计，它可以划分出不同的关注层次，让我们的思考范围能够缩小，更加聚焦于我们要解决的问题核心。反之，数组需要分散精力去考虑数组的下标增减这些细节问题，可能反而掩盖了问题的实质。所以现在很多高级语言，都有对栈的一些封装结构，不用去关心它的实现细节，直接使用各种方法。

1.3 栈的应用

1.3.1 撤销操作

在这里插入图片描述

1.3.2 有效的括号（20）

在这里插入图片描述

思路：

遍历该字符串的每一个字符；
如果是左括号，则存入堆栈；
如果是右括号：
1. 判断堆栈是否非空且栈顶元素为相应的左括号，若匹配则删去栈顶的左括号并继续遍历；
2. 若不满足则返回False；
遍历结束后，若堆栈为空，则返回True，否则返回False。

在这里插入图片描述

栈顶元素反映了在嵌套的层次关系中，最近的需要匹配的元素

class Solution:def isValid(self, s: str) -> bool:# 初始化一个栈stack = []# 遍历每个字符for ch in s:# 左括号则存入堆栈if ch in ['(', '[', '{']:stack.append(ch)else:# 右括号也要先判断堆栈是否为空if stack == []:return False# 是否匹配else:if (ch == ')' and stack[-1] == '(') or (ch == ']' and stack[-1] == '[') or (ch == '}' and stack[-1] == '{'):# 匹配则将栈顶元素弹出stack.pop()else:return False# 堆栈中无剩余符号，即全部匹配才可以返回Trueif stack == []:return Trueelse:return False

class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();  //定义堆栈int length = s.length();  //获取字符串的长度for(int i = 0; i<length; i++){Character a = s.charAt(i);if(a == '(' || a == '{' || a == '['){stack.push(a);}else{if(stack.isEmpty()){return false;}else{if((a == ')' && stack.peek() == '(') || (a == ']' && stack.peek() == '[') || (a == '}' && stack.peek() == '{')){stack.pop();}else{return false;}}}}if(stack.isEmpty()){return true;}else{return false;}}
}

1.3.3 四则运算表达式求值

后缀（逆波兰）表示法所有的符号都是在要运算数字的后面出现

9 +（3-1） 3+10/2
9 3 1 – 3+10 2 / +

后缀表示法的运算规则：

遇到数字就入栈
遇到符号就取出栈顶的两个数stack[-2]和stack[-1]，然后进行运算，如stack[-2] - stack[-1]，然后将计算结果入栈
重复上述步骤直至结束，最后的结果就是运算结果

在这里插入图片描述

python实现如下：

class Solution:def evalRPN(self, tokens):'''四则运算法则:param tokens:后缀表达式:return:计算结果'''# 初始化堆栈stack = []# 遍历每一个字符for ch in tokens:# 如果是符号，则栈顶两个元素出栈做相应的运算if ch in ['+', '-', '*', '/']:b = stack.pop()a = stack.pop()if ch == '+':stack.append(a + b)elif ch == '-':stack.append(a - b)elif ch == '*':stack.append(a * b)else:stack.append(int(a / b))# 如果是数字，则入栈else:# 注意因为后续要运算，所以入栈时要将字符转换为int型stack.append(int(ch)) # 将最后的结果出栈ans = stack.pop()return ans

那么怎么得到后缀表示呢？

中缀表达式 9+（3-1）

3+10/2
后缀表达式 9 3 1 – 3

+10 2 / +

规则：

从左到右遍历中缀表达式每个数字和符号
若是数字就输出，即成为后缀表达式的一部分
若是符号，则判断其与栈顶符号的优先级：
若是右括号或优先级低于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈；
若是左括号或优先级高于栈顶符号，则将该符号入栈
一直到最终输出后缀表达式为止。

在这里插入图片描述

1.3.4 ⭐⭐程序员代码面试指南-设计一个有getMin功能的栈

实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
【要求】
1、 pop、 push、 getMin操作的时间复杂度都是O(1)。
2.、设计的栈类型可以使用现成的栈结构
在这里插入图片描述
解决方法：
俩个栈，一个是普通栈里面放数据stackData，另一个栈里面放栈中最小值stackMin。

第一种方法：
压栈规则：在压栈时判断插入时为空栈或者元素小于等于当前栈顶元素，压入最小值栈中。
出栈规则：如果弹栈元素大小等于（不可能小于）最小值栈顶元素，同时从最小值栈中弹出。
在这里插入图片描述

# 设计一个有getMin功能的栈——方法1
class NewStack1:def __init__(self):# 初始化两个栈self.stackData = []self.stackMin = []def push(self, newNum):# 入栈规则self.stackData.append(newNum)if self.stackMin == [] or newNum <= self.getMin():self.stackMin.append(newNum)def pop(self):# 出栈规则if len(self.stackData) == 0:raise Exception("stack is empty!")value = self.stackData.pop()if value == self.getMin():self.stackMin.pop()return valuedef getMin(self):# stackMin栈的栈顶就是最小值if len(self.stackMin) == 0:raise Exception("stack is empty!")return self.stackMin[-1]

第二种方法：
压栈规则：插入的元素比当前栈中最小值大，将最小值重复入栈。
出栈规则：弹栈时同时弹出数据栈和最小值栈中的一个元素。
在这里插入图片描述

# 设计一个有getMin功能的栈——方法2
class NewStack2:def __init__(self):# 初始化两个栈self.stackData = []self.stackMin = []def push(self, newNum):# 入栈规则self.stackData.append(newNum)if self.stackMin == [] or newNum <= self.getMin():self.stackMin.append(newNum)else:self.stackMin.append(self.getMin())def pop(self):# 出栈规则if len(self.stackData) == 0:raise Exception("stack is empty!")self.stackMin.pop()return self.stackData.pop()def getMin(self):# stackMin栈的栈顶就是最小值if len(self.stackMin) == 0:raise Exception("stack is empty!")return self.stackMin[-1]

二、队列Queue

2.1 队列的定义

队列是一种先进先出的数据结构（先到先得）：First in first out（FIFO）

在这里插入图片描述

2.2 队列的实现

Queue() 创建一个空的队列
enqueue(item) 往队列中添加一个item元素
dequeue() 从队列头部删除一个元素
is_empty() 判断一个队列是否为空
size() 返回队列的大小

class Queue:def __init__(self):self.items = []def is_empty(self):return self.items == []def enqueue(self, item):'''进队列'''self.items.insert(0, item)def dequeue(self):'''出队列'''return self.items.pop()def size(self):'''返回大小'''return len(self.items)if __name__ == "__main__":q = Queue()q.enqueue("hello")q.enqueue("my")q.enqueue("friend")print(q.size())print(q.items)print(q.dequeue())print(q.items)print(q.dequeue())print(q.items)print(q.dequeue())

2.3 数组队列的问题

在这里插入图片描述

如果删除队首元素需要将后面的元素全都往前移动一格的话，时间复杂度将为O(n)。

在这里插入图片描述
而如果只需改变一下队首的指向那么时间复杂度将为O(1)。

2.4 循环队列

2.4.1 循环队列定义

front和tail分别指向队列的队首和队尾的位置，当队列为空时，front == tail

在这里插入图片描述
当有元素加入队列时，放在tail指向的位置，然后tail加一

在这里插入图片描述
删除队首元素后，front指向下一个位置，即front加一

在这里插入图片描述
当队尾放满时，因为队列的前面可能还有一些空间，所以tail可以指向前面的空间，因此，循环队列也可以看做一个环形的队列

在这里插入图片描述

当只剩一个空位置时，就看做队列已经满了，即 (tail + 1)%len(nums) == front 时，队列满，这里取余为的是包括front=0，tail=len(nums) - 1的情况

在这里插入图片描述

2.4.2 循环队列实现

class LoopQueue(object):def __init__(self, n=2):self.arr = [None] * (n + 1)self.front = 0self.tail = 0self.size = 0def __str__(self):return str(self.arr)def __len__(self):return len(self.arr)def __iter__(self):return iter(self.arr)def get_size(self):# 获取队列元素个数return self.sizedef get_capacity(self):# 获取队列容积（实际可存储元素个数）return self.__len__() - 1def is_full(self):# 判断队列是否为满return (self.tail + 1) % len(self.arr) == self.frontdef is_empty(self):# 判断队列是否为空return self.size == 0def get_front(self):# 获取队首return self.arr[self.front]def enqueue(self, e):# 入队if self.is_full():# 如果队列满，以当前队列容积的2倍进行扩容self.resize(self.get_capacity() * 2)self.arr[self.tail] = eself.tail = (self.tail + 1) % len(self.arr)self.size += 1def dequeue(self):# 出队if self.is_empty():raise Exception("Cannot dequeue from an empty queue")result = self.arr[self.front]self.arr[self.front] = Noneself.front = (self.front + 1) % len(self.arr)self.size -= 1# 如果元素个数少于容积的1/4并且还有元素if self.size < self.get_capacity() // 4 and self.get_capacity() > 1:self.resize(self.get_capacity() // 2)return resultdef resize(self, new_capacity):new_arr = [None] * (new_capacity + 1)for i in range(self.size):new_arr[i] = self.arr[(i+self.front) % len(self.arr)]self.arr = new_arrself.front = 0self.tail = self.sizeif __name__ == '__main__':loop_queue = LoopQueue()loop_queue.enqueue("hello")loop_queue.enqueue("my")print(loop_queue.arr)loop_queue.enqueue("friend")print(loop_queue.get_size())print(loop_queue.arr)print(loop_queue.dequeue())print(loop_queue.arr)print(loop_queue.dequeue())print(loop_queue.arr)loop_queue.enqueue("hello")print(loop_queue.arr)loop_queue.enqueue("my")print(loop_queue.arr)loop_queue.enqueue("love")print(loop_queue.arr)print(loop_queue.dequeue())print(loop_queue.dequeue())print(loop_queue.dequeue())print(loop_queue.arr)print(loop_queue.dequeue())print(loop_queue.arr)

结果如下：

['hello', 'my', None]
3
['hello', 'my', 'friend', None, None]
hello
[None, 'my', 'friend', None, None]
my
[None, None, 'friend', None, None]
[None, None, 'friend', 'hello', None]
[None, None, 'friend', 'hello', 'my']
['love', None, 'friend', 'hello', 'my']
friend
hello
my
['love', None, None, None, None]
love
[None, None, None]

2.5 双端队列

2.5.1 双端队列定义

双端队列（deque，全名double-ended queue），是一种具有队列和栈的性质的数据结构。
双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。
在这里插入图片描述

2.5.2 双端队列实现

Deque() 创建一个空的双端队列
add_front(item) 从队头加入一个item元素
add_rear(item) 从队尾加入一个item元素
remove_front() 从队头删除一个item元素
remove_rear() 从队尾删除一个item元素
is_empty() 判断双端队列是否为空
size() 返回队列的大小

class Deque(object):'''双端队列实现'''def __init__(self):self.items = []def is_empty(self):'''判断队列是否为空'''return self.items == []def add_front(self, item):'''在队首添加元素'''self.items.insert(0, item)def add_rear(self, item):'''在队尾添加元素'''self.items.append(item)def remove_front(self):'''从队首删除元素'''return self.items.pop(0)def remove_rear(self):'''从队尾删除元素'''return self.items.pop()def size(self):'''返回队列大小'''return len(self.items)if __name__ == '__main__':deque = Deque()deque.add_front(1)deque.add_front(2)print(deque.items)deque.add_rear(3)deque.add_rear(4)print(deque.items)print(deque.size())print(deque.remove_front())print(deque.remove_front())print(deque.remove_rear())print(deque.remove_rear())

结果如下：

[2, 1]
[2, 1, 3, 4]
4
2
1
4
3

2.6 队列的应用

2.6.1 回文词检测

回文词就是给定一个字符串，从正序和逆序看是对称的。如“上海自来水来自海上”，“山东落花生花落东山”，“asdfdsa”，“123454321”等等。

思路：

将该字符串整体存入双端队列
若队列中剩余的字符数大于1，则取出队首和队尾的字符
若两个字符相等，继续步骤2
若两个字符不相等，返回False，即不是回文词
若队列中剩余的字符数等于1，则退出循环，返回True，即是回文词

def palchecker(aString):'''检测一个字符串是否为回文词'''deque = Deque()# 回文词入队for i in aString:deque.add_front(i)state = True# 双向读取并比较while deque.size() > 1 and state:df = deque.remove_front()dr = deque.remove_rear()if df != dr:state = Falsereturn stateprint(palchecker('abaa'))
print(palchecker("上海自来水来自海上"))

结果为：

False
True

2.6.2 用栈实现队列（232）

在这里插入图片描述

解法一：在一个栈中维持所有元素的出队顺序

思路：
第一种方式是在一个栈中维持所有元素的出队顺序，即所有的元素在入队操作完成后只会保存在一个栈中，且其出栈的顺序和出队的顺序是一致的。下面对入队操作的底层实现进行解释。

要将3加入到队列的队尾：

将s1中的所有元素依次出栈存到s2
将3入栈到s1
再将s2中的所有元素依次出栈存到s1

则s1中的结果就是在队尾将入一个元素的结果：
在这里插入图片描述
出队列就相对比较简单，因为队列是从另一端出，所以就是从栈顶出栈即可。
实现如下：

class MyQueue():def __init__(self):"""Initialize your data structure here."""self._s1, self._s2 = [], []def push(self, x):"""Push element x to the back of queue.:type x: int:rtype: void"""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):"""Remove the element from in front of queue and return that element"""return self._s1.pop()def peak(self):"""Get the front element."""return self._s1[-1]def empty(self):"""Returns whether the queue is empty."""return not self._s1

解法二：一个栈入，一个栈出

思路：
解法二的实现方式与解法一有点不同，按照功能的不同，解法二将两个栈一个用于入队，一个用于出队。假设栈inStack 用于实现入队操作，栈 outStack 用于实现出队操作。

方法二从队尾入队列比较简单，直接往inStack中压栈即可。

而从队首出栈相对麻烦一些：
先判断outStack中是否为空：
若为空，则将inStack中的全部元素依次压入outStack，再从outStack的栈顶出栈一个元素
若不为空，直接从outStack的栈顶出栈一个元素
在这里插入图片描述

class MyQueue():def __init__(self):"""Initialize your data structure here."""self._in_stack, self._out_stack, self._front = [], [], Nonedef push(self, x):"""Push element x to the back of queue:type x: int:rtype: void"""if not self._in_stack:self._front = xself._in_stack.append(x)def pop(self):"""Removes the element from in front of queue and returns that element.:rtype: int"""if self.empty():raise Exception("[ERROR] The queue is empty!")if not self._out_stack:while self._in_stack:self._out_stack.append(self._in_stack.pop())return self._out_stack.pop()def peek(self):"""Get the front element.:rtype: int"""if self.empty():raise Exception("[ERROR] The queue is empty!")if not self._out_stack:return self._frontelse:return self._out_stack[-1]def empty(self):"""Returns whether the queue is empty.:rtype: bool"""return not self._in_stack and not self._out_stack

class MyQueue {Stack<Integer> stack1 = new Stack<>();Stack<Integer> stack2 = new Stack<>();public MyQueue() {}public void push(int x) {stack1.push(x);}public int pop() {if(stack2.isEmpty()){int length = stack1.size();for(int i=0; i<length; i++){stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {if(stack2.isEmpty()){int length = stack1.size();for(int i=0; i<length; i++){stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack2.isEmpty() && stack1.isEmpty();}
}/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj = new MyQueue();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.peek();* boolean param_4 = obj.empty();*/

2.6.3 滑动窗口最大值（239）

在这里插入图片描述

可以使用双指针的知识：同向双指针——固定长度滑动窗口（会超时）

现在也可以使用队列的知识：
现有一个双向队列名为qmax当我们遍历到数组的第i个元素的时候，有如下规则:

如果qmax为空，直接插入i。
如果qmax不为空，则获取qmax队尾的坐标，记为j。
如果a[j] > a[i]，说明队尾的值比他数组大，则直接插入队列。
如果a[j]<= a[i]，需要把j从qmax弹出，然后会到第二步，再决定插入的策略。

# 生成窗口最大数组
def getMaxWindow(arr, w):# 除去非法输入if arr == None or w < 1 or len(arr) < w:return# 初始化qmax = []res = []# 遍历for i in range(len(arr)):# 非空且遇到更大的就把小的弹出，否则直接插入while qmax and arr[qmax[-1]] <= arr[i]:qmax.pop()qmax.append(i)# 丢弃用不到的索引if qmax[0] <= i - w:qmax.pop(0)# 达到窗口长度后，开始将最大值存入res中if i - w + 1 >= 0:res.append(arr[qmax[0]])return res