栈和队列

一、栈

1.1 定义

​ 栈式限制在一端进行插入和删除操作的线性表，具有先进后出的特性，如图所示：

1.2 基本概念

• 判断栈是否为空：$ node $ 为栈的头结点，若 \(node\) 为空，返回 \(True\) , 否则返回 \(False\)
• 入栈：入栈即为在栈的顶部插入元素
• 出栈： 出栈即为删除顶部的元素
• 取出栈顶元素： 即为获取栈顶的元素

1.3 顺序栈

1、初始化

​ 顺序栈在初始化时要定义栈的大小。设定 max 为栈的存储元素个数

• 栈为空时， self.top 的数值为 -1 ；
• 栈为满时， self.top = max - 1

​  代码如下：

class SeqStack(object):
def __init__(self, max):
    # 顺序栈的最大容量
    self.max =max
    # 当栈为空时， 栈定指针指向 -1
    self.top = -1
    # 存储栈元素的数组
    self.stack = [None for i in range(self.max)]

2. 判断栈是否为空

​ 如果 self.top 的数值为 -1 ，则表示空战， 返回 True，否则返回 False，代码如下：

def empty(self):
  return self.top is -1

3. 入栈

• 栈满 ： 抛出异常
• 栈不满： 将 top 值加一，将新的值放进去

代码如下：

def push(self, val):
  if self.top == self.max - 1:
    raise IndexError('栈已满')
  else:
    # 将栈顶指针加一
    self.top += 1
    self.stack[self.top] = val

4. 出栈

• 栈空：抛出异常
• 栈不空：将self.top 的数值减 1

代码如下：

def pop(self):
  if self.empty():
    raise IndexError('栈空')
  else:
    #　此时top指向栈顶元素，存下栈顶元素的值，再将指针下移一个位置
    cur = self.stack[self.top]
    sef.top -= 1
    return cur

5. 取出栈顶元素

• 栈空：抛出异常
• 栈不空：返回栈顶元素

代码如下：

def peek(self):
  if self.empty():
    raise IndexError('栈空！')
  else:
    return self.stack[self.top]

1.3 链栈

　　链栈为栈的链式存储结构，是运算受限的单链表，其插入和删除操作只能在表头位置进行。设链栈头指针为top，初始化top=None。

​ 链栈节点结构与单链表节点结构相同，如图所示：

1. 初始化

• 栈节点初始化：

class Node(object):
  def __init__(self, val):
    # 节点的数据域
    self.val = val
    # 节点的指针域
    self.next = None

• 栈初始化

class LinkedStack(object):
  def __init__(self):
    self.top = None

2. 判断栈是否为空

def empty(self):
  return self.top is None

3. 入栈

​ 将待插入节点的 next 指针指向栈顶指针所指向的节点，将栈顶指针指向新节点，代码如下:

def push(self, val):
  """
  :param val: 入栈元素
  """
  newNode = Node(val)
  # 新节点的直接后继指向栈顶指针
  newNode.next = self.top
  # 将栈顶指针指向新节点
  self.top = newNode

4. 出栈

• 栈空：抛出异常
• 栈不空：将栈顶元素出栈，将栈顶指针指向当前栈顶元素的下一个节点

代码如下：

def pop(self):
  """
  ：return: 返回栈顶元素
  """
  # 如果栈为空，则抛出异常
  if self.empty():
    raise IndexError('栈为空')
  else:
    # temp用来存储栈顶元素
    temp = self.top
    # 指针指向栈顶的下一个元素
    setf.top = self.top.next
    return temp

5. 取出栈顶元素

def peek(self):
  """
  :return : 返回栈顶元素
  """
  if self.empty():
    raise IndexError('栈为空')
  else:
    return self.top.val

二、队列

2.1 定义

​ 队列只允许在一端进行插入，在另一端进行删除，具有先进先出的特性。、

2.2 基本概念

• 队首： 允许删除的一端称为队首
• 队尾： 允许插入的一端称为队尾
• 入队： 插入元素的过程称为入队
• 出队： 删除袁术的过程称为出队
• 空队列： 当队列中没有元素时称为空队列

2.3 顺序队列

　　在顺序队列中，将元素入队时，只需要在队尾添加一个元素即可。但是，如果将元素出队，则除了将元素从队首删除之外，还需要将其他元素向前移动一个位置。

1. 基本概念

　队列初始化时，规定了队列的最大元素容量为6。\(self.front、self.rear\)均指向下标为0的位置，如图所示:

class SeqQueue(object):
  def __init__(self, max):
    self.max = max
    self.front = 0
    self.rear = 0
    self.data = [None for i in range(self.max)]

3. 插入元素

　现在向队列中添加3个元素，分别是5、3、7，添加元素后的队列如图所示：

　每次插入都是在队尾插入的，也就是rear所在的位置。每次插入完成后rear自增1。现将队列中的所有元素出队，如图所示：

4. 假溢出

　 将队列中所有元素出队后，队列的起始位置已经由原本下标为0的位置移动到下标为3的位置了。那么，如果继续按这样入队、出队的形式，是不是到最后会存在这样一种现象—队列中是空的，没有任何元素，却无法继续将元素进队？结果是显而易见的，最后就是会出现这种现象。这种现象叫作假溢出。

5. 循环队列

　 为了解决假溢出现象，引入了循环队列的概念。所谓循环队列，就是将队列首尾连接起来。当rear的数值超过数组的最大长度时，先判断front是否在下标为0的位置，如果不在，则将rear指向下标0。

​ 为方便理解，将循环队列表示为一个环形的图，起始时， rear 和 front 指向下标 0 ，如图所示：

　 现在向队列中添加5个元素，分别是5、3、7、8、4。在循环队列中，添加元素也是在队尾添加的，即rear下标处，如图所示：

​ 从循环队列中删除两个元素，删除元素是在队首删除的，如图所示：

这里的解决方法是保留一个元素空间，当队列满时，还有一个空的位置。由于rear有可能比front大，也有可能比front小，所以尽管相差一个位置，其实有可能是相差一整圈。
若队列的最大容量为max，则队满的条件是（rear+1）%max==front

6. 循环队列初始化

　self.front 指向队首下标，self.rear 指向队尾下标，max 表示队列的最大容量。循环队列初始化代码实现如下：

class CircleQueue(object):
  def __init__(self, max):
    # 队列最大容量
    self.max = max
    # 存储队列元素的数组
    self.data = [None for i in range(self.max)]
    # 队首指针
    self.front = 0
    # 队尾指针
    self.rear = 0

7. 循环队列的基本操作

• 判断队空

def empty(self):
  return self.front == self.rear

• 入队
  • 队满：抛出异常
  • 队不满：插入元素，并且self.rear 自增 1，若self + 1 大于 max，则将 self.rear 指向下标0 。

def push(self, val):
  """
  :param val:待插入的关键字
  """
  if (self.rear + 1) % self.max == self.front:
    raise IndexError('队满')
  # 在队尾插入新的关键字
  self.data[self.rear] = val
  # 修改队尾指针
  self.rerr = (self.rear + 1) % self.max

• 出队
  • 队空：抛出异常
  • 队不空：获取队首元素，队首指针加一，返回队首元素

​ 代码如下：

def pop(self):
  if self.empty():
    raise IndexError('队空')
  # 队列不为空，获取队首元素
  cur = self.data[self.front]
  # 修改队首指针，指向下一个位置
  self.front = (self.front + 1) % self.max
  # 返回原队首元素
  return cur

• 获取队首元素
  • 队空：抛出异常
  • 队不空： 返回队首元素

​ 代码如下：

def peek(self):
  if self.empty():
    raise IndexError('队空')
  return self.data[self.front]

2.3 链式队列

　　顺序队列在插入和删除时需要移动大量的元素，因此引入了链式队列。链式队列插入和删除操作方便，不需要移动元素，只需要改变指针的指向即可。

　　链式队列节点结构与单链表的节点结构一样，队列节点包括一个数据域data和一个指针域 next。节点结构如图所示：

1. 初始化

• 节点类Node初始化

class Node(object):
  def __init__(self, data):
    self.data = data
    self.next = None

• 队列初始化: 对于不带头节点的链式队列，初始化时，链式队列的front指针指向None。

class LinkedQueue(object):
  def __init__(self):
    self.front = None

2. 判断队空

def empty(self):
  return self.front is None

3. 入队

• 队空：将队首指针指向待插入的新节点
• 队不空：则遍历到队尾，将新节点插入到队尾

代码如下：

def push(self, val):
  new = Node(val)
  if self.front == None:
    raise IndexError('队空！')
  else:
    cur = self.front
    # 遍历队列
    while cur.next != None:
      cur = cur.next
    # 在队尾插入元素
    cur.next = new

4. 出队

　判断队列是否为空，若队列为空，则抛出异常，否则删除队首节点，代码实现如下

def pop(self):
  if self.empty():
    raise IndexError('队空')
  else:
    cur = self.front
    # 将队首指针指向队首节点的后继节点
    self.front = self.front.next
    return cur

5. 获取队首元素

　判断队列是否为空，若队列为空，则抛出异常；若队列不为空，则返回队首元素，代码实现如下

def peek(self):
  if self.empty():
    raise IndexError('队空')
  els：
  return self.front.data

总结

• 栈是一种限制只能在栈顶进行插入和删除操作的线性表，具有先进后出的特性，各种运算的时间复杂度均为O(1)。
• ​队列是一种只允许在队尾进行插入、只允许在队首进行删除的线性表，具有先进先出的特性。其插入和删除的时间复杂度均为O(1)。
• 循环队列就是首尾连接起来的队列。假设存储队列的空间大小为n，则只能存n-1个元素，这是为了方便判断队空与队满。循环队列有如下规定：
  • 若队首指针与队尾指针相同，则表示队空。
  • 若队头指针在队尾指针的下一个位置，则表示队满。