Python用list实现堆栈和队列

Python中可以用list来模拟栈和队列:

  • 栈(stack):只能在一端进行数据操作,遵循后进先出(LIFO)原则
  • 队列(queue):可以在两端进行数据操作,遵循先进先出(FIFO)原则,出队列的一端称为队首,入队列的一端称为队尾

一、栈

1、栈要记录的数据

  • 栈顶位置top:注意这个top有两种理解方式,一种是表示栈的最后一个数据的位置,另一种是表示栈的最后一个数据的下一个位置,这两种理解对栈的操作代码有一定的影响
  • 栈最大大小size

2、栈的操作

  • isEmpty():判断栈是否为空
  • isFull():判断栈是否已满
  • push(element):向栈中添加一个值,注意栈是否为满的
  • pop():从栈中弹出一个值,注意栈是否为空

3、Python列表实现栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class StackException(Exception):
def __init__(self, data):
self.data = data
def __str__(self):
return self.data

class Stack(object):
def __init__(self,size = 10):
self.S = []
self.size = size # 栈大小
self.top = -1 # 栈顶位置

def setSize(self, size):
# 设置栈的大小
self.size = size

def isEmpty(self):
# 判断栈是否为空
if self.top == -1:
return True
else:
return False

def isFull(self):
# 判断栈是否满
if self.top == self.size - 1:
return True
else:
return False

def peek(self):
# 查看栈顶的对象,但不移除
if self.isEmpty():
raise StackException('StackUnderflow')
else:
element = self.S[-1]
return element

def pop(self):
# 移除栈顶对象,并返回该对象的值
if self.isEmpty():
raise StackException('StackUnderflow')
else:
element = self.S[-1]
self.top = self.top - 1
del self.S[-1]
return element

def push(self, element):
# 把对象压入栈顶
if self.isFull():
raise StackException('StackOverflow')
else:
self.S.append(element)
self.top = self.top + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
if __name__ == '__main__':
s = Stack()
# 压栈测试
for i in range(10):
s.push(i)
# 栈满测试
try:
s.push(1)
except Exception as e:
print(e)
# 出栈测试
for i in range(10):
print(s.pop())
# 栈空测试
try:
s.pop()
except Exception as e:
print(e)

二、队列

1、队列要记录的数据

  • 队头位置end
  • 队列的大小size

2、标准做法

利用数组Q[1..n]来实现含有n-1个元素队列(保留一位元素用来判断队列空或满)。该列有一个属性Q.head指向队头元素,属性Q.tail指向下一个新元素将要插入的位置,列中的元素存放在位置Q.head, Q.head+1, …, Q.tail-1上。

  • 初始时,Q.head = Q.tail = 1
  • Q.head = Q.tail时, 队列为空
  • Q.head = Q.tail + 1时,队列为满

3、队列的操作

  • isEmpty():判断队列是否为空
  • isFull():判断队列是否已满
  • inQueue(element):入队
  • outQueue():出队

4、Python列表实现队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class QueueException(Exception):
def __init__(self, data):
self.data = data
def __str__(self):
return self.data

class Queue(object):
def __init__(self, size=10):
self.Q = []
self.size = size # 队列大小
self.end = -1 # 队头位置

def setSize(self, size):
# 设置队列的大小
self.size = size

def inQueue(self, element):
# 对象入队
if self.end < self.size - 1:
self.Q.append(element)
self.end += 1
else:
raise QueueException('QueueFull')

def outQueue(self):
# 对象出队
if self.end == -1:
raise QueueException('QueueEmpty')
else:
element = self.Q[0]
self.Q = self.Q[1:]
self.end -= 1
return element
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
if __name__ == '__main__':
q = Queue()
# 入队测试
for i in range(10):
q.inQueue(i)
# 队列满测试
try:
q.inQueue(1)
except Exception as e:
print(e)
# 出队测试
for i in range(10):
print(q.outQueue())
# 队列空测试
try:
q.outQueue()
except Exception as e:
print(e)
赞赏一杯咖啡
0%