python数据结构之栈与队列

python数据结构之栈与队列

用list实现堆栈stack

堆栈:后进先出

如何进?用append

如何出?用pop()

>>>
>>> stack = [3, 4, 5]
>>> stack.append(6)
>>> stack.append(7)
>>> stack
[3, 4, 5, 6, 7]
>>> stack.pop()
7
>>> stack
[3, 4, 5, 6]
>>> stack.pop()
6
>>> stack.pop()
5
>>> stack
[3, 4]

用list实现队列queue

队列:先进先出

如何进?用append

如何出?用popleft()

>>>
>>> from collections import deque
>>> queue = deque(["Eric", "John", "Michael"])
>>> queue.append("Terry") # Terry arrives
>>> queue.append("Graham") # Graham arrives
>>> queue.popleft() # The first to arrive now leaves
'Eric'
>>> queue.popleft() # The second to arrive now leaves
'John'
>>> queue # Remaining queue in order of arrival
deque(['Michael', 'Terry', 'Graham'])

自定义堆栈

栈是限定仅在表尾进行插入或删除操作的线性表。对于栈来说,表尾称为栈顶,表头称为栈底。不含元素的空表称为空栈。

堆栈ADT(抽象数据类型)一般提供以下接口:

函数 说明
Stack() 创建堆栈
push(item) 向栈顶插入项
pop() 删除栈顶的项
clear() 清空堆栈
is_empty() 判断堆栈是否为空
size() 返回堆栈中项的个数
top() 返回栈顶的项
print() 打印堆栈

python数据结构之栈与队列

class Stack(object):
"""堆栈"""
def __init__(self, item = []):
self.item = []
if len(item):
for i in item:
self.item.append(i) def push(self, item):
self.item.append(item) def clear(self):
del self.item def is_empty(self):
return self.size() == 0 def size(self):
return len(self.item) def print(self):
print(self.item) def top(self):
return self.item[-1] def pop(self):
data = self.top()
self.item.pop()
return data print("创建堆栈")
stack = Stack([1,2,3])
stack.print()
print("向栈顶插入元素")
stack.push(4)
stack.print()
print("判断堆栈是否为空")
print(stack.is_empty())
print("返回堆栈中项的个数")
print(stack.size())
print("返回栈顶的项")
print(stack.top())
print("删除栈顶的项")
stack.pop()
stack.print()
print("清空堆栈")
print(stack.clear())

程序输出:

创建堆栈
[1, 2, 3]
向栈顶插入元素
[1, 2, 3, 4]
判断堆栈是否为空
False
返回堆栈中项的个数
4
返回栈顶的项
4
删除栈顶的项
[1, 2, 3]
清空堆栈
None

自定义队列

队列是一种先进先出的线性表。它只允许在表的一端进行插入,在另一端删除元素。

队列ADT(抽象数据类型)一般提供以下接口:

函数 说明
Queue() 创建队列
enqueue(item) 向队列插入元素
dequeue() 删除队列的元素
clear() 清空队列
is_empty() 判断队列是否为空
size() 返回队列中项的个数
print() 打印队列
class Queue(object):
"""模拟队列"""
def __init__(self, item = []):
self.item = []
if len(item):
for i in item:
self.item.append(i) def enqueue(self, item):
self.item.append(item) def dequeue(self):
self.item.pop(0) def clear(self):
del self.item def is_empty(self):
return self.size() == 0 def size(self):
return len(self.item) def print(self):
print(self.item) print("创建队列")
queue = Queue([1,2,3])
queue.print()
print("向队列插入元素")
queue.enqueue(4)
queue.print()
print("从队列中删除元素")
queue.dequeue()
queue.print()
print("判断队列是否为空")
print(queue.is_empty())
print("返回队列中项的个数")
print(queue.size())
queue.print()
print("清空队列")
print(queue.clear())

程序输出结果:

创建队列
[1, 2, 3]
向队列插入元素
[1, 2, 3, 4]
从队列中删除元素
[2, 3, 4]
判断队列是否为空
False
返回队列中项的个数
3
[2, 3, 4]
清空队列
None

参考

《数据结构》严蔚敏

https://docs.python.org/3.6/tutorial/datastructures.html#more-on-lists

上一篇:让编辑器支持word的复制黏贴,支持截屏的黏贴


下一篇:cp 提示 overwrite 问题