lickylin 2020-02-23
##################################################
""" 三、线性结构 (1)栈 1、定义:栈是一个数据集合,可以理解为只能在一端进行插入或者删除操作的列表。 2、栈的特点:后进先出(last-in,first-out),简称LTFO表 这种数据结构的特点: 就是像是杯子或者是弹夹,电梯, 存储的时候从底部开始,读取的时候从顶部开始,具备这种特点就是栈 就是后进先出, 存储的时候就可以从顺序表或者链表就可以实现, 只让从一端去存储,和读取,就实现了栈, 3、栈的概念: 栈顶:允许插入和删除的这一端称之为栈顶 栈底:另一固定的一端称为栈底 空栈:不含任何元素的栈称为空栈 4、栈的基本操作: 进栈(压栈):push 出栈:pop 取栈顶:gettop 5、栈的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())
##########################################
##########################################