栈和队列基本原理

• 1.栈
• • 1.1 栈基本原理
  • 1.2. 栈操作步骤
  • • 1.2.1 插入数据流程【压栈】
    • 1.2.2 移除数据流程【出栈】
  • 1.3. 栈代码实现
• 2.队列
• • 2.1 队列基本原理
  • 2.2 队列操作步骤
  • • 2.2.1 插入数据
    • 2.2.2 移除数据
  • 2.3. 队列代码实现
• 3.栈与队列对比

1.栈

1.1 栈基本原理

• 栈顶【末尾】，栈底【开头】
• 栈的三条约束
  • 只能从末尾插入数据【压栈】
  • 只能从末尾移除数据【出栈】
  • 只能从末尾读取数据
• 特性：后进先出(LIFO last in,first out)【最后入栈的元素，最先出栈】

1.2. 栈操作步骤

1.2.1 插入数据流程【压栈】

1.2.2 移除数据流程【出栈】

1.3. 栈代码实现

• 栈实现

  # Stack()创建一个空的新栈。它不需要参数，并返回一个空栈。
  class Stack():def __init__(self):  # 创建一个空栈self.items = []def push(self, item):  # 压栈self.items.append(item)def pop(self):  # 出栈return self.items.pop()def peek(self):  # 返回栈顶元素下标return len(self.items) - 1def isEmpty(self):#测试栈是否为空return self.items == ''def size(self): #返回栈中的item数量return len(self.items)s = Stack()
  s.push(5)
  print("压栈第1个元素后，栈的数据:",s.items)
  s.push(3)
  print("压栈第2个元素后，栈的数据:",s.items)
  s.push(0)
  print("压栈第3个元素后，栈的数据:",s.items)
  print('*'*50)
  print("出栈第1个元素后，栈的数据:",s.items,";出现的数值为:",s.pop())
  print("出栈第2个元素后，栈的数据:",s.items,";出现的数值为:",s.pop())
  print("出栈第3个元素后，栈的数据:",s.items,";出现的数值为:",s.pop())
  

• 通过队列实现栈

  class Queue():def __init__(self):self.items = []def enqueue(self, item):self.items.append(item)def dequeue(self):return self.items.pop(0)def isEmpty(self):return self.items == ''def size(self):return len(self.items)items = [1, 2, 3, 4, 5]
  q1 = Queue()
  q2 = Queue()
  for item in items:q1.enqueue(item)print("压栈",q1.items)
  while True:while q1.size() > 1:item = q1.dequeue()q2.enqueue(item)print("出栈",q1.dequeue())q1, q2 = q2, q1if q1.size() == 0:break
  

  

2.队列

2.1 队列基本原理

• 栈顶【末尾】，栈底【开头】
• 栈的三条约束
  • 只能从末尾插入数据【压栈】
  • 只能从开头移除数据【出栈】
  • 只能从开头读取数据
• 特性：先进先出(FIFO first in,first out)【最先入栈的元素，最先出栈】

2.2 队列操作步骤

2.2.1 插入数据

2.2.2 移除数据

2.3. 队列代码实现

• 队列

  # 创建队列类
  class Queue():def __init__(self):self.items=[]def enqueue(self,item): #压栈self.items.append(item)def dequeue(self): # 出栈return self.items.pop(0)def isEmpty(self): #查看队列是否为空。return self.items==''def size(self): #return len(self.items)q=Queue()
  q.enqueue(5)
  print("压栈第1个元素后，队列的数据:",q.items)
  q.enqueue(3)
  print("压栈第2个元素后，队列的数据:",q.items)
  q.enqueue(0)
  print("压栈第3个元素后，队列的数据:",q.items)
  print('*' * 50)
  print("出栈第1个元素后，队列的数据:", q.items, ";出现的数值为:", q.dequeue())
  print("出栈第2个元素后，队列的数据:", q.items, ";出现的数值为:", q.dequeue())
  print("出栈第3个元素后，队列的数据:", q.items, ";出现的数值为:", q.dequeue())
  

• 通过栈实现队列

  class Stack():def __init__(self):  # 创建一个空栈self.items = []def push(self, item):  # 从栈顶【-1】添加到栈底【0】self.items.append(item)def pop(self):  # 从栈顶向栈底取元素return self.items.pop()def peek(self):  # 返回栈顶元素下标return len(self.items) - 1def isEmpty(self):return self.items == ''def size(self):return len(self.items)s1=Stack()
  s2=Stack()
  items=[1,2,3,4,5]
  for item in items:s1.push(item)print("压栈", s1.items)
  while s1.size()>0:item=s1.pop()s2.push(item)print("出栈", s1.items)
  

3.栈与队列对比

• 栈与队列相同
  • 插入数据【栈与队列都从末尾】
• 栈与队列不同
  • 读取数据【栈从末尾，队列从开头】
  • 移除数据【栈从末尾，队列从开头】