文章目录

一、栈1、定义2、特点3、栈结构实现1）栈的操作2）python实现 二、队列1、定义2、特点3、队列结构实现1）操作2）python实现操作 三、双端队列1、定义2、操作3、python实现操作 对于栈和队列：不用关心物理存放是什么样的，只需要关心这两种数据结构支持什么样的操作，操作有什么特点

一、栈

1、定义

栈，可以利用任意一种线性表来实现，是一种数据结构，用来保存线性数据，可以存入数据、访问数据、删除数据。

2、特点

栈数据结构只允许在容器的一端进行加入数据和输出数据，因此对数据的访问顺序为后进先出（LIFO，Last In First Out）[可以链表，也可以顺序表]

3、栈结构实现

栈可以用顺序实现，也可以用链表实现 用python中的顺序表list实现栈

1）栈的操作

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

2）python实现

给栈中添加元素为压栈或入栈–push 从栈取出栈顶元素为弹出元素–pop python基础中，可以直接判断返回True or False 的为：空字符串、0、空字典、空元组、空列表

class Stack(object): """栈""" def __init__(self): """构造一个容器当作栈存放数据""" self.__list=[] def push(self,item): """添加一个新的元素item到栈顶""" # 根据栈的特点，将列表的尾部当作栈尾，存取数据都从列表尾部进行 # 这里选择list作为栈容器，可以从列表头部存取，也可以从尾部存取 # 但是根据列表的特性，从尾部存取时间复杂度为O(1)，头部为O(n),所以选择列表尾部存取 self.__list.append(item) def pop(self): """弹出栈顶元素""" # 栈顶即栈尾 return self.__list.pop() def peek(self): """返回栈顶元素""" # 由于空列表没有list[-1]，所以先判空 if self.__list: return self.__list[-1] else: return None def is_empty(self): """判断栈是否为空""" return self.__list==[] # return not self.__list 当self.__list为空时，return self.__list 返回False，所以这里返回True def size(self): """返回栈的元素个数""" return len(self.__list)

测试：

if __name__ == '__main__': s=Stack() s.push(1) s.push(2) s.push(3) s.push(4) print(s.pop()) print(s.pop()) print(s.pop()) print(s.pop())

结果：

4 3 2 1

二、队列

1、定义

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表

2、特点

队列是一种先进先出(FIFO，First In First Out)的线性表，允许插入的一端为队尾，允许删除的一端为对头，队列不允许在中间进行操作

3、队列结构实现

1）操作

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

2）python实现操作

class Queue(object): """队列""" def __init__(self): """构造队列容器，存储数据""" self.__list=[] def enqueue(self,item): """往队列添加一个item元素""" self.__list.append(item) # self.__list.add(item) # 队列的特点为一端添加元素，一端删除元素 # 考虑时间复杂度的条件下，到底选哪个方法添加和弹出时， # 根据实际使用情况，删除数据多还是添加数据操作频繁 def dequeue(self): """从队列头部删除一个元素""" return self.__list.pop(0) # return self.__list.pop() def is_empty(self): """判断队列是否为空""" return self.__list==[] def size(self): """返回队列的大小""" return len(self.__list)

测试：

if __name__ == '__main__': q=Queue() q.enqueue(1) q.enqueue(2) q.enqueue(3) q.enqueue(4) print(q.dequeue()) print(q.dequeue()) print(q.dequeue()) print(q.dequeue())

结果：

1 2 3 4

三、双端队列

1、定义

双端队列（deque）,是一种具有队列和栈的性质的数据结构

2、操作

Deque() 创建一个空的双端队列add_front(item) 从对头加入一个item元素add_rear(item) 从队尾加入一个item元素remove_front() 从对头删除一个item元素remove_rear() 从队尾删除一个item元素is_empty() 判断双端队列是否为空size() 返回队列的大小

3、python实现操作

class Deque(object): """双端队列""" def __init__(self): self.__list=[] def add_front(self,item): """往队列头部添加一个item元素""" self.__list.insert(0,item) def add_rear(self,item): """往队列尾部添加一个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 == [] def size(self): """返回队列的大小""" return len(self.__list)