##################################################三、线性结构（1）栈1、定义：栈是一个数据集合，可以理解为只能在一端进行插 ################################################## """三、线性结构（1）栈
##################################################
"""三、线性结构（1）栈1、定义：栈是一个数据集合，可以理解为只能在一端进行插入或者删除操作的列表。2、栈的特点：后进先出（last-in，first-out），简称LTFO表这种数据结构的特点:就是像是杯子或者是弹夹，电梯，存储的时候从底部开始，读取的时候从顶部开始，具备这种特点就是栈就是后进先出，存储的时候就可以从顺序表或者链表就可以实现，只让从一端去存储，和读取，就实现了栈，3、栈的概念：栈顶：允许插入和删除的这一端称之为栈顶栈底：另一固定的一端称为栈底空栈：不含任何元素的栈称为空栈4、栈的基本操作：进栈（压栈）：push出栈：pop取栈顶：gettop5、栈的Python实现不需要自己定义，使用列表结构即可。进栈函数：append出栈函数：pop查看栈顶元素：li[-1]"""################## python使用list实现栈 #######################
############################################## 栈的实现# 使用list实现class Stack(object): """栈""" def __init__(self): self.__list = [] # 私有的，不允许外部操作，使用list作为容器， def is_empty(self): """判断是否为空""" return self.__list == [] # 这是返回一个判断，如果是一个空列表就是返回true，否则就是false， def push(self, item): """加入元素""" self.__list.append(item) # 选择在尾部添加，尾部添加效率高， def pop(self): """弹出元素""" return self.__list.pop() def peek(self): """返回栈顶元素""" if self.__list: # 做一个判断如果不是空列表返回数据，空列表返回none return self.__list[-1] else: return None def size(self): """返回栈的大小""" return len(self.__list)if __name__ == "__main__": stack = Stack() stack.push("hello") stack.push("world") stack.push("itcast") print(stack.size()) print(stack.peek()) print(stack.pop()) print(stack.pop()) print(stack.pop())##################################################
"""（2）队列1、介绍队列是一个数据集合，仅允许在列表的一端进行插入，另一端进行删除，进行插入的一端称为队尾（rear），插入动作称之为进队或入队进行删除的一端称之为对头（front），删除动作称为出队双向队列：对列的两端都允许进行进队和出队操作2、队列的实现队列能否简单用列表实现？为什么？初步设想：列表+两个下标指针创建一个列表和两个变量，front变量指向队首，rear变量指向队尾。初始时，front和rear都为0。进队操作：元素写到li[rear]的位置，rear自增1。出队操作：返回li[front]的元素，front自减1。"""################## python使用list实现队列 #######################
# 队列的实现# 取值的一端是队头，存入值的是队尾，class Queue(object): """队列""" def __init__(self): self.__list = [] def is_empty(self): return self.__list == [] def enqueue(self, item): """进队列""" self.__list.insert(0, item) def dequeue(self): """出队列""" return self.__list.pop() def size(self): """返回大小""" return len(self.__list)if __name__ == "__main__": q = Queue() q.enqueue("hello") q.enqueue("world") q.enqueue("itcast") print(q.size()) print(q.dequeue()) print(q.dequeue()) print(q.dequeue())################## python会用list实现双端队列 #######################
# 双端队列，class Deque(object): """双端队列""" def __init__(self): self.__list = [] def is_empty(self): """判断队列是否为空""" return 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 size(self): """返回队列大小""" return len(self.__list)if __name__ == "__main__": deque = Deque() deque.add_front(1) deque.add_front(2) deque.add_rear(3) deque.add_rear(4) print(deque.size()) print(deque.pop_front()) print(deque.pop_front()) print(deque.pop_rear()) print(deque.pop_rear())##########################################
##########################################
数据结构和算法-数据结构-线性结构-栈和队列