基础数据结构：栈和队列

栈、队列和双端队列

1. 栈

  定义： 堆栈（stack）又称为栈 或 堆叠，是计算机科学中的一种抽象资料类型，只允许在有序的线性资料集合的一端（称为堆栈顶端，top）进行加入数据（push）和移除数据（pop）的运算。因而按照后进先出（LIFO, Last In First Out）的原理运作，堆栈常用一维数组或链接串列来实现。常与另一种有序的线性资料集合队列相提并论。用户可以在任何时刻向栈中插入一个对象，但只能取得或者删除最后一个插入的对象（即栈顶）。下面是一个使用到堆栈的实例。

例1-1： 文本编辑器通常提供一个“撤销“机制以取消最近的编辑操作并返回到先前的文本状态。这个撤销操作就是通过将文本的变化状态保存在一个栈中得以实现的。

1.1 栈的抽象数据类型

  栈是最简单也最重要的数据结构，它被广泛地应用到一系列不同的应用中，并在许多更加复杂的数据结构和算法中充当工具。从形式上来说，栈是支持以下两种操作的抽象数据类型（ADT），用S来表示这一ADT实例：

• S.push(e): 将一个元素e添加到栈S的栈顶。
• S.pop(e): 从栈S中移除并返回栈顶的元素，如果此时栈是空的，这个操作将出错。此外，为了方便，我们定义了以下访问方法：
• S.top(): 在不移除栈顶元素的情况下，返回一个栈S的栈顶元素；若栈为空，这个操作将出错。
• S.is_empty(): 如果栈中不包含任何元素，则返回一个布尔值 “True”
• len(S): 返回栈S中元素的数量；在Python中，我们用__len__这个特殊方法实现它。 按照惯例，我们假定一个新创建的栈是空的，并且其容量也没有预先的限制。添加进栈的元素可以是任何类型的。

1.2 简单的基于数组的栈实现

  我们可以简单地通过在Python列表中存储一些元素来实现一个栈。list类已支持append方法，用于添加一个元素到列表底部，并且支持pop方法，用于移除列表中最后的元素，所以我们可以很自然地将一个列表的尾部与一个栈的顶部相对应起来。这样我们就简单地实现了一个栈的模拟。

st = [5, 1, 4]

# 使用 append() 向栈顶添加元素
st.append(2)
st.append(3)
# >>> st
# [5, 1, 4, 2, 3]

# 使用 pop 取出栈顶元素
st.pop()
# >>> st
# [5, 1, 4, 2]

# 使用 clear 清空栈
st.clear()

虽然程序员可以直接用一个list类代替一个正式的stack类，但是列表还包括一些不符合这种抽象数据类型的方法（比如：增加或者移除处于列表任何位置的元素）。同时，list类所使用的术语也不能与栈这种抽象数据类型的传统命名方法精确对应，特别是append方法和push方法之间的区别。相反，我们将强调如何使用一个列表实现栈元素的内部存储，并同时提供一个符合堆栈的公共接口。

栈方法	用Python列表实现
S.push(e)	L.append(e)
S.pop()	L.pop()
S.top()	L[-1]
S.is_empty()	len(L) == 0
len(S)	len(L)

用Python列表作为存储实现一个栈

class ArrayStack:
    def __init__(self):
        self.data = []
    
    def __len__(self):
        return len(self.data)
    
    def is_empty(self):
        return len(self.data) == 0
    
    def push(self,e):
        self.data.append(e)

    def top(self):
        if self.is_empty():
            raise Empty('Stack is empty')
        return self.data[-1]

    def pop(self):
        if self.is_empty():
             raise Empty('Stack is empty')
        return self.data.pop()

1.3 基于栈的一些应用

例1-2 LeetCode 20. 有效的括号（Easy）

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"

输出：true

示例 2：

输入：s = "()"

输出：true

示例 3：

输入：s = "(]"

输出：false

  思路一：

自左到右，我们可以逐一判断该字符串内的每个括号，如果是左括号，那么我们就将它压入一个栈中，如果是右括号，那么我们就判断这个右括号和栈顶的左括号是否匹配，如果是，就弹出栈顶括号，如果不是，就返回false。

记住，我们的栈是一个只储存左括号的栈，原因是右括号如果入栈，那么它将再也弹不出去

最后，如果这个字符串是有效的，那么我们就得到了一个空栈，反之则无效。

  代码实现：

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        match_dic = {')':'(', ']':'[', '}':'{'}
        temp_list = []

        for ch in s:
            if ch in '([{':
                temp_list.append(ch)
            elif ch in ')]}':
                # 右括号比左括号先出现, 不能闭合
                if not temp_list:
                    return False

                # 遇到右括号, 必然要与上一个左括号闭合, 如果不匹配就 False
                if match_dic[ch] == temp_list[-1]:
                    temp_list.pop(-1)
                else:
                    return False
        # 正常闭合的情况下, 栈里面应该全都弹出去了, 所以应该是空的
        if not temp_list:
            return True
        else:
            return False

  思路二：

如果一个字符串是有效的括号，那么它就会在中间出现一个'[]' 或 '{}' 或 '()'结构，当我们删去这些结构后，余下的仍然是一个有效括号。因此，我们可以对一个有效的括号不断进行该操作，直到字符串变空。

  代码实现：

class Solution:
    def isValid(self, s):
        while '{}' in s or '()' in s or '[]' in s:
            s = s.replace('{}', '')
            s = s.replace('[]', '')
            s = s.replace('()', '')
        return s == ''

例1-3 LeetCode 402. 移掉K位数字（Medium）

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

示例 1 ：

输入： num = "1432219", k = 3

输出："1219"

解释： 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。

示例 2 ：

输入： num = "10200", k = 1

输出："200"

解释： 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

示例 3 ：

输入： num = "10", k = 2

输出："0"

解释： 从原数字移除所有的数字，剩余为空就是 0 。

  思路： 我们知道，对于两个数1234a6和1234b6，如果a大于b，那么前者就大于后者，反之则小于。也就是说，在两个位数相同的数中，相同位第一个不同的数字大小决定了两个数的大小，那么我们就可以有如下想法：维护单调递增栈。

具体实现过程如下：

我们从头扫字符串的每位数字，如果一个数字比栈顶的数字大，那么它就应该入栈，反之，则弹出栈顶数字，再压入该数。弹出k次后停止，此时即为所求。如果没有经过k次就停止了，我们取前n-k位作为我们的答案，因为我们得到了单调递增栈，后面的数不会比前面的更小。

  代码实现：

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stk = []
        for c in num:
            while stk and c < stk[-1] and k:
                stk.pop()
                k -= 1
            stk.append(c)
        res = ''.join(stk)[:len(stk) - k].lstrip('0')
        return res if res else '0'
# 注：字符串的.lstrip方法可以用来去除字符串左侧的指定字符和特定序列。
# 与之类似的，rstrip方法可以去除右侧的，strip方法可以去除两侧的。

例1-3 LeetCode 321. 拼接最大数 （Hard）

给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。

求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。

说明: 请尽可能地优化你算法的时间和空间复杂度。

示例 1:

输入:

nums1 = [3, 4, 6, 5]

nums2 = [9, 1, 2, 5, 8, 3]

k = 5

输出:

[9, 8, 6, 5, 3]

示例 2:

输入:

nums1 = [6, 7]

nums2 = [6, 0, 4]

k = 5

输出:

[6, 7, 6, 0, 4]

示例 3:

输入:

nums1 = [3, 9]

nums2 = [8, 9]

k = 3

输出:

[9, 8, 9]

  思路：

pass

  代码实现：

pass

2. 队列

  队列（queue）是另一种基本的数据结构，它与栈互为“表亲”关系，队列是由一系列对象组成的集合，这些对象的插入和删除遵循先进先出（First in First out, FIFO)的原则。也就是说，元素可以在任何时刻进行插入，但是只有处在队列最前面的元素才能被删除。

  我们通常将队列中允许插入的一段称为队尾（rear），将允许删除的一段称为队头（front）。对这个属于的一个形象比喻就是一堆人在排队进入游乐场。人们从队尾插入排队等待进入游乐场，而从这个队的队头进入游乐场。

2.1 队列的抽象数据类型

  通常来说，队列的抽象数据类型定义了一个包含一系列对象的集合，其中元素的访问和删除被限制在队列的第一个元素，而且元素的插入被限制在序列的尾部。这个限制根据FIFO原则执行元素的插入和删除操作。对于队列Q而言，队列的抽象数据类型支持如下两个基本方法：

• Q.enqueue(e): 向队列Q的队尾添加一个元素。
• Q.dequeue(): 从队列Q中移除并返回第一个元素，如果队列为空，则触发一个错误。

队列的抽象数据类型还包括如下方法（第一个类似堆栈的top方法）：

• Q.first(): 在不移除的前提下返回队列的第一个元素；如果队列为空，则触发一个错误。
• Q.is_empty(): 如果队列Q没有包含任何元素则返回布尔值“True”。
• len(Q): 返回队列Q中元素的数量；在Python中我们通过__len__这个特殊方法实现。

2.2 基于数组的队列实现

  对于栈这种抽象数据结构类型，我们用Python列表作为底层存储创造了一个非常简单的适配器类，也可以使用类似的方法支持一个队列的抽象数据类型。我们可以用append(e)方法将e添加至列表的尾部。当一个元素退出队列后，我们可以使用pop(0)来移除列表中的第一个元素。

  这是非常简单的实现方式，因此它也最为低效。我们知道，当pop操作在一个列表中以非索引的方式调用时，可以通过执行一个循环将所有在特定索引另一边的元素转移到它的左边，目的是为了填补由pop操作给序列造成的“洞”。因此，一个pop(0)操作的调用总是处于最坏的情况，耗时为O(n)

  我们可以改进上面的策略，完全避免调用pop(0)。可以用一个指代为空的指针代替这个数组中离队的元素，并且保留一个显式的变量f来存储当前在最前面的元素的索引。这样一个算法对于离队操作而言耗时为O(1)。然而这种方法仍有一个缺点：如果我们允许队列的前端远离索引0，那么随着不断地删除添加操作，底层数组的大小将逐渐增长到O(m)，其中m值等于自队列创建以来对队列进行追加元素操作的总和，而不是当前队列中元素的数量。这种设计会在一些所需队列的大小相对稳定却被长时间使用的程序中产生不利的影响。

  循环使用数组

  为了开发一种更为健壮的队列实现方法，我们让队列的前端不断趋向数组的右端，同时让队列内的元素在底层数组尾部“循环”。我们假定底层数组的长度为固定值N，它比实际队列中元素的数量大。新的元素在当前队列的尾部利用入队操作进入队列，逐步将元素从队列的前面插入到索引为N-1的位置，然后紧接着时索引为0的位置，接着是索引为1的位置，下表所示为一个第一个元素为E最后一个元素为M的队列，可用于说明这一过程。

I	J	K	L	M	...	E	F	G	H
0	1	2				f			N-1

  实现这种循环的方法并不困难。当从队列中删除一个元素并欲更新前面的索引时，我们可以使用算式f=(f+1)%N进行计算。例如：有一个长度为10的列表，有一个索引为7的首部，我们可以计算(7+1)%10 == 8来更新首部。

  Python队列的实现方法

  在接下来的代码段中，我们给出了通过使用Python列表以循环的方式来实现一个队列的抽象数据类型的完整方法。其中，这个队列类维护如下3个实例变量:

• _data:指一个固定容量的列表实例。
• _size:是一个整数，代表当前存储在队列内的元素的数量。
• _front:是一个整数，代表_data实例队列中的第一个索引。它被初始化为0.

class ArrayQueue:
    DEFAULT_CAPACITY = 10

    def __init__(self):
        self._data = [None] * ArrayQueue.DEFAULT_CAPACITY
        self._size = 0
        self._front = 0

    def __len__(self):
        return self._size

    def is_empty(self):
        return self._size == 0

    def first(self):
        if self.is_empty():
            raise Empty('Queue is empty')
        return self._data[self._front]
    
    def dequeue(self):
        if self.is_empty():
            raise Empty('Queue is empty')
        answer = self._size[self._front] 
        self._data[self.front] = None
        self._front = (self._front + 1) % len(self._data)
        self._size -= 1
        return answer

    def enqueue(self,e):
        if self._size == len(self._data):
            self._resize(2 * len(self._data))
        avail = (self._front + self._size) % len(self._data)
        self._data[avail] = e
        self._size += 1

    def _resize(self,cap):
        old = self._data
        self._data = [None] * cap
        walk = self._front
        for k in range(self._size):
            self._data[k] = old[walk]
            walk = (1 + walk) % len(old)
        self._front = 0

注： 在上述的实现过程中我们发现，当在队列满的状态下调用enqueue操作时，底层的存储数组就要进行扩展，但是调用dequeue操作时却并不会进行缩减数组的大小的处理。这样处理的结果是，底层的存储数组的大小是队列曾存储的最多元素的个数，而不是当前元素的个数。

  无论什么时候，当所存储的元素降低导数组总存储能力的1/4时，一个健壮的方法是将这个数组大小缩减到当前容量的一半。这一处理可以通过在dequeue发那个发中插入如下两行代码来实现。

if 0 < self._size < len(self._data) // 4:
    self._resize(len(self._data) // 2)

2.3 双端队列

  接下来考虑一个类队列数据结构，它支持在队列的头部和尾部都进行插入和删除操作，这样一种结构被称为双端队列（double-ended queue 或者 deque）。

  双端队列的抽象数据类型比栈和队列的抽象数据类型要更普遍。在一些应用中，这些额外的普遍性是非常有用的，例如使用一个队列来描述餐馆当中的等餐队列。

  使用环形数组实现双端队列

  我们可以使用上述代码段提供的ArrayQueue类相同的方法来实现队列的抽象数据类型。这个ADT应该支持如下方法：

• D.add_first(e): 向双端队列的前面添加一个元素e。
• D.add_last(e): 向双端队列的后面添加一个元素e。
• D.delete_first(): 从双端队列中移除并返回第一个元素。若双端队列为空，则触发一个错误。
• D.delete_last(): 从双端队列中移除并返回最后一个元素。若双端队列为空，则触发一个错误。

  此外，双端队列的抽象数据类型还包括如下的方法：

• D.first(): 返回（但不移除）双端队列的第一个元素。若双端队列为空，则触发一个错误。
• D.last(): 返回（但不移除）双端队列的最后一个元素。若双端队列为空，则触发一个错误。
• D.is_empty(): 如果双端队列不包括任何一个元素，则返回布尔值“True”。
• len(D): 返回当前双端队列中的元素个数。在Python中，我们用__len__这个特殊方法实现它。

  我们不在此赘述具体的代码实现方式，无论什么时候，只要想直到双端队列的尾部索引，或者超过队尾的第一个可用的位置，我们就可以通过模运算计算得出。例如，方法last()就是用如下索引公式来实现的

back = (self._front + self._size - 1) % len(self._data)

  Python collections模块中的双端队列

  Python的标准collections模块中包含对一个双端队列类的实现方法，它是位于collections模块中的deque类，我们可以通过from collections import deque来访问它。下表给出了我们构造的双端队列与deque类的比较。

我们的双端队列ADT	collections.deque	描述
len(D)	len(D)	元素数量
D.add_first()	D.appendleft()	加到开头
D.add_last()	D.append()	加到结尾
D.delete_first()	D.popleft()	从开头移除
D.delete_last()	D.pop()	从结尾移除
D.first()	D[0]	访问第一个元素
D.last()	D[-1]	访问最后一个元素
	D[j]	通过索引访问任意一项
	D[j] = val	通过索引修改任意一项
	D.clear()	清除所有内容
	D.rotate(k)	循环右移k步
	D.remove(e)	移除第一个匹配的元素
	D.count(e)	统计对于e匹配的数量

注1： rotate方法被描述为“循环右移k步”，它相当于对数组中每个元素整体右移k个长度，到达数组尾部后循环到开头。

注2： 库函数队列的构造函数同样支持一个可选的maxlen参数以建立一个固定长度的双端队列（deque(maxlen=10)）。然而，当双端队列满时，如果在队列的任意一端调用append方法，它并不会触发一个错误；相反，这会导致在相反一段移除一个元素。也就是说，当队列满时，调用appendleft方法会导致右端一个隐藏的pop调用发生，以便为新加入的元素腾出空间。下面给出了一些简单的实例。

from collections import deque

# 创建一个包含一些元素的 deque
my_deque = deque([1, 2, 3, 2, 4, 5])

# 在指定位置插入元素
my_deque.insert(2, 99)

# 移除指定值的第一个匹配项
my_deque.remove(2)

# 返回指定值的第一个匹配项的索引
index = my_deque.index(4)

# 返回指定值的出现次数
count = my_deque.count(2)

# 反转 deque 中的元素
my_deque.reverse()

# 输出结果
print(my_deque)   # 输出: deque([5, 4, 99, 3, 1])
print(index)      # 输出: 1
print(count)      # 输出: 0（因为 2 已被移除）

# rotate的应用
from collections import deque

# 创建一个包含一些元素的 deque
my_deque = deque([1, 2, 3, 4, 5])

# 向右循环移动两步
my_deque.rotate(2)
print(my_deque)  # 输出: deque([4, 5, 1, 2, 3])

# 向左循环移动一步
my_deque.rotate(-1)
print(my_deque)  # 输出: deque([5, 1, 2, 3, 4])

# maxlen的应用
from collections import deque

# 创建一个最大长度为 3 的 deque
my_deque = deque(maxlen=3)

# 向 deque 中添加元素
my_deque.append(1)
my_deque.append(2)
my_deque.append(3)

print(my_deque)  # 输出: deque([1, 2, 3])

# 超过最大长度，会自动删除左侧元素
my_deque.append(4)
print(my_deque)  # 输出: deque([2, 3, 4])

  双栈模拟队列

  还有一种冷门的方法是使用两个 栈 来模拟一个队列。

  这种方法使用两个栈 F, S 模拟一个队列，其中 F 是队尾的栈，S 代表队首的栈，支持 push（在队尾插入），pop（在队首弹出）操作：

  push：插入到栈 F 中。

  pop：如果 S 非空，让 S 弹栈；否则把 F 的元素倒过来压到 S 中（其实就是一个一个弹出插入，做完后是首尾颠倒的），然后再让 S 弹栈。

  容易证明，每个元素只会进入/转移/弹出一次，均摊复杂度 O(1)。