基于python语言的数据结构之堆栈与队列的实现
# 堆栈的实现
# -*- coding: utf-8 -*-
"""
栈（stack）， 是一种容器，可以存入数据元素，访问元素，删除元素
只允许在容器的一段存取数据
特点： 后进先出 Last in first out
"""
"""
借助list来实现堆栈
添加的方法； 压栈（入栈）
弹栈（出栈）
Stack() 创建一个新的空栈
push(item) 添加一个新元素 item 到栈顶
pop() 弹出栈顶元素
peek() 返回栈顶元素
is_empty() 判断栈是否为空
size() 返回栈元素的个数
"""
class Stack(object):
"""栈"""
def __init__(self):
self.__list = []
def push(self, item):
"""添加一个新元素item到栈顶"""
self.__list.append(item) # 尾部添加 ，时间复杂度o1
# self.__list.insert(0,item) 这样从尾部添加的时间复杂度为O(n)
def pop(self):
"""弹出栈顶元素"""
return self.__list.pop()
def peek(self):
"""返回栈顶元素"""
if self.__list:
return self.__list[-1]
return None
def is_empty(self):
"""判断栈是否为空"""
return self.__list == []
def size(self):
"""返回栈元素的个数"""
return len(self.__list)
if __name__ == '__main__':
s = Stack()
print(s.is_empty())
s.push(1)
s.push(3)
s.push(4)
print(s.pop())
print(s.pop())
print(s.pop())
# 队列的实现
# -*- coding: utf-8 -*-
class Queue:
"""队列"""
def __init__(self):
self.__list = []
def enqueue(self, item):
"""往队列中添加一个元素"""
self.__list.append(item) # 时间复杂度o(1)
def dequeue(self):
"""从队列头部删除一个元素"""
return self.__list.pop(0) # 时间复杂度 o(n)
def is_empty(self):
"""判断是否为空"""
return self.__list == []
def size(self):
"""返回队列大小"""
return len(self.__list)
if __name__ == '__main__':
s = Queue()
print(s.is_empty())
s.enqueue(1)
s.enqueue(3)
s.enqueue(4)
print(s.dequeue())
print(s.dequeue())
print(s.dequeue())
# 双端队列的实现
# -*- coding: utf-8 -*-
class Deque(object):
def __init__(self):
self.__list = []
def add_front(self, item):
"""往队列头部添加一个元素"""
self.__list.insert(0, item) # 时间复杂度o(1)
def add_rear(self, item):
"""往队列尾部添加一个元素"""
self.__list.append(item) # 时间复杂度o(1)
def pop_rear(self):
"""从队列尾部删除一个元素"""
return self.__list.pop() # 时间复杂度 o(1)
def pop_front(self):
"""从队列头部删除一个元素"""
return self.__list.pop(0) # 时间复杂度 o(n)
def is_empty(self):
"""判断是否为空"""
return self.__list == []
def size(self):
"""返回队列大小"""
return len(self.__list)