1.队列定义
队列是一种特殊的线性表,它只允许在表的前端进行删除操作,在表的后端进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。
队列特征:
先进先出FIFO(frist-in, frist-out)
2.顺序队列
顺序队列:是一种用顺序表模拟实现的队列存储结构。
他的定义是用一组地址连续的存储单元,依次存放从队头到队尾的数据元素。
基本操作:
- 入队push
- 出队pop
- 队空
self.rear == self.front - 队满
(self.rear + 1) % maxsize == self.front
如果用列表如何表示
class Queue():
def __init__(self, size):#初始化一个空队列
self.size = size
self.front =0
self.rear = 0
self.queue = []
def push(self, x): # 入队操作
if self.is_fulled():
print("queue is full")
return False
else:
self.queue.append(x)
self.rear = self.rear + 1
return True
def pop(self): # 出队操作
if self.is_empty():
print("queue is empty")
return False
else:
# head = self.queue[self.front]
# self.front = self.front + 1
# return head
return self.queue.pop(self.front)
def is_fulled(self):
return self.rear - self.front + 1 == self.size
def is_empty(self):
return self.front == self.rear
def get_head(self):
if self.is_empty():
return False
else:
return self.queue[self.front]
def show(self):
print(self.queue)
q= Queue(10)
print("初始化队列为空",q.is_empty())
for i in range(10):
q.push(i)
q.show()
print("插入十个元素后,队满",q.is_fulled())
print(q.pop())
print(q.pop())
3.循环队列
将顺序队列的头尾相接。解决队列的空间浪费问题。
基本操作:
- 入队push
- 出队pop
- 队空
self.rear == self.front - 队满
(self.rear + 1) % maxsize == self.front
class Queue:
def __init__(self, size=100):
self.queue = [0 for _ in range(size)]
self.size = size
self.rear = 0 # 队尾指针
self.front = 0 # 队首指针
# 入队
def push(self, element):
if not self.is_filled():
self.rear = (self.rear + 1) % self.size
self.queue[self.rear] = element
else:
raise IndexError("Queue is filled.")
# 出队
def pop(self):
if not self.is_empty():
self.front = (self.front + 1)% self.size
return self.queue[self.front]
else:
raise IndexError("Queue is empty.")
# 判断队空
def is_empty(self):
return self.rear == self.front
# 判断队满
def is_filled(self):
return (self.rear + 1) % self.size == self.front
def show(self):
print(self.queue)
q = Queue(5)
for i in range(4):
q.push(i)
print(q.show())
print(q.pop())
结果: