1.栈的总结
- 栈是一个满足只允许(后进先出的)规则的线性表，当我们用数组实现时，称为顺序栈，当我们用链表实现时，就称为链栈。
- 栈形象点就像一个仓库，我们每次放东西都放在深处，这样慢慢的，越靠近门口的东西反而是越新的，这样就是后进先出。
2. 下面我们用代码来实现模拟顺序栈
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
#模拟顺序栈的基本操作
class stack:
def __init__(self):
self.stack = [] #用列表来表示
# 入栈
def push(self,data):
self.stack.append(data)
# 出栈
def pop(self):
return self.stack.pop(0)
# 清空栈
def clear(self):
return self.stack.clear()
# 遍历栈
def printStack(self):
print(self.stack)
return self.stack
# 判断栈是否为空
def isEmpty(self):
return False if self.stack else True
s = stack()
s.push(1)
s.push(2)
s.push(3)
s.push(4)
s.printStack()
s.pop()
s.printStack()
s.pop()
s.printStack()
s.clear()
print(s.isEmpty())
s.printStack()
3.链栈的实现
用单链表来创建链栈，在链表头部进行插入和删除操作。 链表的创建可以看上面的文章
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
56
57
58
59
## 先定义节点
class Node:
# 初始化节点的值
def __init__(self, data):
self.data = data
self.next = None
# 获得节点的值
def getData(self):
return self.data
# 获得下个节点的指针
def getNext(self):
return self.next
# 设置节点的值
def setData(self, newData):
self.data = newData
# 设置下一个节点
def setNext(self, nextNode):
self.next = nextNode
class Stack:
def __init__(self):
self.head = None
# 入栈
def push(self,data):
temp = Node(data) # 建造一个节点，并初始值为data
temp.setNext(self.head) # 节点指针指向头指针
self.head = temp
# 出栈
def pop(self):
if self.head == None:
return -1
else:
data = self.head.getData()
self.head = self.head.getNext()
return data
# 判断是否为空
def isEmpty(self):
return True if self.head == None else False
# 遍历
def print(self):
l = []
current = self.head
while current!=None:
l.append(current.getData())
current = current.getNext()
return l
s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s.print())
print(s.pop())
print(s.print())
print(s.isEmpty())
4.队列是什么
- 队列是一种只允许(队头)删除，(队尾)插入的线性结构,符合先进先出。
4.1 下面是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
class Queue:
def __init__(self):
self.items = []
# 判空
def isEmpty(self):
return self.items == []
# 入队
def enqueue(self,item):
self.items.insert(0,item)
# 出队
def dequeue(self):
return self.items.pop()
# 判断队列长度
def size(self):
return len(self.items)
def print(self):
print(self.items)
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.print()
print(q.dequeue())
q.print()
q.enqueue(4)
q.print()
print(q.isEmpty())
4.2 我们来设计循环队列
-
判断循环队列为空的公式:rear==front
-
判断循环队列满的公式:(rear+1) % QueueSize==front
-
计算队列长度:rear-front+QueueSize）% QueueSize
-
入队：（rear+1）% QueueSize
-
出队：（front+1）% QueueSize
4.3 循环队列的代码
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
56
57
58
59
60
61
62
63
64
# 定义一个节点
class Node:
# 初始化节点的值
def __init__(self, data):
self.data = data
self.next = None
# 获得节点的值
def getData(self):
return self.data
# 获得下个节点的指针
def getNext(self):
return self.next
# 设置节点的值
def setData(self, newData):
self.data = newData
# 设置下一个节点
def setNext(self, nextNode):
self.next = nextNode
class queue:
def __init__(self,QueueSize):
self.arr = [None]*(QueueSize+1)#牺牲一个储存单元来，辨别空还是满
self.front = 0 # 队头指针
self.rear = 0 # 队尾指针
# 入队
def enqueue(self,data):
QueueSize = len(self.arr)
self.arr[self.rear] = data
self.rear = (self.rear+1)%QueueSize
# 出队
def dequeue(self):
QueueSize = len(self.arr)
self.arr[self.front] = None
self.front = (self.front+1)%QueueSize
# 判断是否空队列
def isEmpty(self):
return True if self.rear == self.front else False
# 判断是否满度列
def isFull(self):
QueueSize = len(self.arr)
return True if self.front == (self.rear+1)%QueueSize else False
# 判断已经存储的长度
def size(self):
return (self.rear - self.front+len(self.arr))% len(self.arr)
q = queue(3)
q.enqueue(1)
q.enqueue(2)
print(q.size())
q.enqueue(3)
print(q.arr)
print("队满",q.isFull())
q.dequeue()
print(q.arr)
q.dequeue()
print(q.arr)
q.dequeue()
print(q.arr)
print("队空",q.isEmpty())
