数据结构和算法-数据结构-线性结构-栈和队列
2023-09-14 09:00:33 时间
##################################################
""" 三、线性结构 (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())
##########################################
##########################################
相关文章
- 经典算法题每日演练——第九题 优先队列
- Java实现 蓝桥杯VIP 算法训练 和为T
- Java实现 蓝桥杯 算法提高 队列操作
- 【python cookbook】【数据结构与算法】5.实现优先级队列
- 各种排序算法汇总
- 重新整理数据结构与算法——单双链表模拟队列[四]
- 机器学习笔记:k近邻算法介绍及基于scikit-learn的实验
- Atitit Queue consum algo 队列消费算法fifo lifo ro目录1. 队列消费算法 11.1. FIFO 先入先出 11.2. LIFO 后入先出 不能多开 1
- Algorithm:C++语言实现之队列相关算法(最短路径条数问题、拓扑排序)
- 从软件工程的角度写机器学习2——流行的机器学习应用模式与算法
- DataScience:数据预处理/特征工程之线性变换—四种特征缩放Scaling算法简介、标准化standardization、归一化Normalization的概述与区别
- 二进制数据的贝叶斯非参数聚类算法(Matlab代码实现)
- 数据挖掘十大算法
- 【算法竞赛刷题模板12】单调队列
- 数据结构与算法之队列
- 数据结构和算法 四、队列