算法与数据结构(part5)--栈与队列

学习笔记，仅供参考，有错必纠

---

文章目录

算法与数据结构–基于python栈栈是什么栈(ADT)的操作栈的实现 队列队列是什么队列的操作队列的实现 双端队列双端队列是什么双端队列的操作双端队列的实现

---

算法与数据结构–基于python

栈

栈是什么

栈的概念

栈(stack)是一种容器，可存入数据元素、访问元素、删除元素。

它的特点在于只能允许在容器的一端(称为栈顶端指标)进行加入数据(push)和输出数据(pop)的运算。

没有了位置概念，保证任何时候可以访问、删除的元素都是此前最后存入的那个元素，确定了一种默认的访问顺序。

由于栈数据结构只允许在一端进行操作，因而按照后进先出(Last In First Out)的原理运作，简称LIFO。

图示

栈(ADT)的操作

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

栈的实现

定义一个栈：

class Stack: # 初始化空栈 def __init__(self): self.__list = [] def push(self, item): self.__list.append(item) def pop(self): if self.__list: return self.__list.pop() else: return None def peek(self): if self.__list: return self.__list[-1] else: return None def is_empty(self): return self.__list is None def size(self): return len(self.__list) if __name__ == '__main__': s = Stack() s.push(1) s.push(2) s.push(3) print(s.pop()) print(s.pop()) print(s.pop())

输出：

3 2 1

队列

队列是什么

队列的概念 队列(queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。队列是一种先进先出的(First In First Out)的线性表，简称FIFO。 图示

队列的操作

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

队列的实现

定义一个队列：

# 定义队列 class Queue: # 初始化 def __init__(self): self.__list = [] def enqueue(self,item): self.__list.append(item) def dequeue(self): return self.__list.pop(0) def is_empty(self): return self.__list is None def size(self): return len(self.__list) if __name__ == '__main__': q = Queue() q.enqueue(1) q.enqueue(2) q.enqueue(3) print(q.dequeue()) print(q.dequeue()) print(q.dequeue())

输出：

1 2 3

双端队列

双端队列是什么

双端队列的概念

双端队列(deque，全名double-ended queue)，是一种具有队列和栈的性质的数据结构。

双端队列中的元素可以从两端弹出，插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。

图示

双端队列的操作

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

双端队列的实现

class Deque: def __init__(self): self.__list = [] def add_front(self,item): self.__list.insert(0,item) def add_rear(self,item): self.__list.append(item) def pop_front(self): return self.__list.pop(0) def pop_rear(self): return self.__list.pop() def is_empty(self): return self.__list is None def size(self): return len(self.__list) if __name__ == '__main__': d = Deque() d.add_front(1) d.add_front(2) d.add_rear(3) d.add_rear(4) print(d.size()) print(d.pop_front()) print(d.pop_front()) print(d.pop_rear()) print(d.pop_rear())

输出：

4 2 1 4 3