Python堆栈和队列|极客笔记

Python堆栈和队列

数据结构在计算机中组织存储，以便我们可以轻松访问和更改数据。堆栈（Stacks）和队列（Queues）是计算机科学中最早定义的数据结构。一个简单的Python列表既可以充当队列又可以充当堆栈。队列遵循先进先出（FIFO）规则，并用于编程进行排序。堆栈和队列通常使用数组或链表进行实现。

堆栈

堆栈是一个遵循后进先出（LIFO）原则的数据结构。实现堆栈需要两个简单的操作：

推入（push） – 它将一个元素添加到堆栈的顶部。
弹出（pop） – 它将一个元素从堆栈的顶部移除。

Python堆栈和队列

操作：

添加 – 它向堆栈中添加项目并增加堆栈大小。添加操作发生在堆栈顶部。
删除 – 它包括两个条件，首先，如果堆栈中没有元素，则堆栈会发生下溢，并且其次，如果堆栈包含一些元素，则最顶部的元素将被移除。它会减小堆栈大小。
遍历 – 它涉及访问堆栈的每个元素。
特征：
堆栈的插入顺序会被保留。
用于解析操作。
允许重复。

代码

# Code to demonstrate Implementation of 
# stack using list 
x = ["Python", "C", "Android"] 
x.push("Java") 
x.push("C++") 
print(x) 
print(x.pop()) 
print(x) 
print(x.pop()) 
print(x)

输出：

['Python', 'C', 'Android', 'Java', 'C++']
C++
['Python', 'C', 'Android', 'Java']
Java
['Python', 'C', 'Android']

队列

队列遵循先进先出（FIFO）原则。它从两端打开，因此我们可以轻松地在后端添加元素，并从前端删除元素。

为了实现队列，我们需要两个简单的操作：

enqueue – 将一个元素添加到队列的末尾。
dequeue – 从队列的开头移除元素。

Python堆栈和队列

队列操作

添加 – 在队列中添加元素，位置在队列的末尾。
删除 – 有两种情况 – 如果队列中没有元素，则发生下溢 (Underflow) ，或者如果队列中包含一些元素，则删除位于前面的元素。
遍历 – 遍历队列中的每个元素。

特性

队列中保留了插入的顺序。
允许重复。
有助于解析CPU任务操作。

注意：队列的实现方式略有不同。队列遵循“先进先出”的原则。时间是一个重要因素。栈是快速的，因为我们从列表的末尾插入和弹出元素，而在队列中，插入和弹出操作是从列表的开头进行的，因此变得较慢。这个时间差异是由于列表的属性造成的，在末尾操作上速度较快，而在开始操作上速度较慢，因为所有其他元素必须逐个移动。

代码

import queue 
# Queue is created as an object 'L'
L = queue.Queue(maxsize=10) 

# Data is inserted in 'L' at the end using put() 
L.put(9) 
L.put(6) 
L.put(7) 
L.put(4) 
# get() takes data from 
# from the head  
# of the Queue 
print(L.get()) 
print(L.get()) 
print(L.get()) 
print(L.get())

输出: