数据结构-队列
1. 定义：
队列是一种遵循先进先出（FIFO, First In First Out）原则的线性数据结构。在队列中，元素从一端添加（队尾），从另一端移除（队头）。
class Queue:
def __init__(self):
self.items = []
- 主要操作：
队列的主要操作包括enqueue（向队尾添加元素）、dequeue（从队头移除元素）和dequeue（查看队头元素），以及isEmpty（检查队列是否为空）。 - enqueue
def enqueue(self, item):
self.items.append(item)
- dequeue
def dequeue(self):
if not self.is_empty():
return self.items.pop(0)
else:
print("Queue is empty")
return None
- dequeue1
def dequeue1(self):
return self.items[0]
- isEmpty
def is_empty(self):
return len(self.items) == 0
此处判断队和栈方法不一样的原因：
在 Python 中，队列（Queue）和栈（Stack）都可以使用列表（List）来实现。在这两种数据结构中，is_empty() 方法都是用来检查数据结构是否为空的。
-
对于栈来说，使用 self.items == [] 来检查是否为空是因为栈是一种后进先出（LIFO）的数据结构，也就是说最后进入栈的元素会最先被取出。所以如果栈为空，那么 self.items 列表应该是空的。
-
而对于队列来说，使用 len(self.items) == 0 来检查是否为空是因为队列是一种先进先出（FIFO）的数据结构，也就是说最先进入队列的元素会最先被取出。虽然也可以使用 self.items == [] 来检查队列是否为空，但是在一些情况下，使用 len(self.items) == 0 更为直观和清晰。
总的来说，这两种方式都可以用来检查数据结构是否为空，选择哪种方式取决于个人偏好和代码的清晰度。
3. 特性：
队列提供了一种按照元素添加顺序处理数据的方式。它限制了元素的访问顺序，确保最先添加的元素最先被处理。
4. 应用：
队列广泛应用于数据处理和任务调度领域，如操作系统的任务调度、打印队列管理、网络请求处理等。
5. 变体：
队列有多种变体，包括循环队列（在固定大小的队列中循环使用空间）、优先级队列（元素按照优先级出队）、双端队列（两端都可以进队和出队）。
- 循环队列：
class CircularQueue:
def __init__(self, capacity):
self.capacity = capacity
self.queue = [None] * capacity
self.front = self.rear = -1
def enqueue(self, item):
if (self.rear + 1) % self.capacity == self.front:
print("队列已满")
elif self.front == -1:
self.front = 0
self.rear = 0
self.queue[self.rear] = item
else:
self.rear = (self.rear + 1) % self.capacity
self.queue[self.rear] = item
def dequeue(self):
if self.front == -1:
print("队列为空")
elif self.front == self.rear:
temp = self.queue[self.front]
self.front = -1
self.rear = -1
return temp
else:
temp = self.queue[self.front]
self.front = (self.front + 1) % self.capacity
return temp
def display(self):
if self.front == -1:
print("队列为空")
elif self.rear >= self.front:
for i in range(self.front, self.rear + 1):
print(self.queue[i], end=" ")
print()
else:
for i in range(self.front, self.capacity):
print(self.queue[i], end=" ")
for i in range(0, self.rear + 1):
print(self.queue[i], end=" ")
print()
# 示例用法
cq = CircularQueue(5)
cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(3)
cq.enqueue(4)
cq.enqueue(5)
cq.display()
cq.dequeue()
cq.dequeue()
cq.enqueue(6)
cq.enqueue(7)
cq.display()
- 优先级队列：
import heapq
class PriorityQueue:
def __init__(self):
self.queue = []
self.index = 0
def push(self, item, priority):
heapq.heappush(self.queue, (-priority, self.index, item))
self.index += 1
def pop(self):
return heapq.heappop(self.queue)[-1]
# 示例用法
pq = PriorityQueue()
pq.push('task1', 5)
pq.push('task2', 1)
pq.push('task3', 3)
print(pq.pop()) # 输出：task1
print(pq.pop()) # 输出：task3
- 双端队列：
from collections import deque
# 创建一个双端队列
d = deque()
# 两端进队
d.append(1) # 右端进队
d.appendleft(2) # 左端进队
# 两端出队
print(d.pop()) # 右端出队，输出：1
print(d.popleft()) # 左端出队，输出：2