上查看所有课程
队列是编程中非常有用的数据结构。它类似于电影院外的排队购票，先进入队列的人最先买到票。
队列遵循先进先出 (FIFO) 规则——先进入队列的元素也是先出队列的元素。
在上图中，由于 1 先于 2 入队，它也是最先出队的。它遵循FIFO规则。
在编程术语中，将元素放入队列称为enqueue（入队），从队列中移除元素称为dequeue（出队）。
我们可以在任何编程语言（如 C、C++、Java、Python 或 C#）中实现队列，但规范基本相同。
队列的基本操作
队列是一个对象（一种抽象数据结构 - ADT），它允许进行以下操作：
- Enqueue（入队）：将元素添加到队列的末尾
- Dequeue（出队）：从队列的前端移除元素
- IsEmpty（判空）：检查队列是否为空
- IsFull（判满）：检查队列是否已满
- Peek（查看）：获取队列前端元素的值而不移除它
队列的工作原理
队列操作的工作原理如下：
- 两个指针 FRONT 和 REAR
- FRONT 指向队列的第一个元素
- REAR 指向队列的最后一个元素
- 初始时，将 FRONT 和 REAR 的值设置为 -1
入队操作
- 检查队列是否已满
- 对于第一个元素，将 FRONT 的值设置为 0
- 将 REAR 索引加 1
- 将新元素添加到 REAR 指向的位置
出队操作
- 检查队列是否为空
- 返回 FRONT 指向的值
- 将 FRONT 索引加 1
- 对于最后一个元素，将 FRONT 和 REAR 的值重置为 -1
Python、Java、C 和 C++ 中的队列实现
我们通常使用数组在 Java 和 C/C++ 中实现队列。在 Python 中，我们使用列表。
队列可视化：不要只看不练。使用我们新的 DSA 可视化工具，实时查看数据结构的每一行如何一步步工作。 自己试试！
# Queue implementation in Python
class Queue():
def __init__(self, k):
self.k = k
self.queue = [None] * k
self.head = self.tail = -1
# Insert an element into the queue
def enqueue(self, data):
if (self.tail == self.k - 1):
print("The queue is full\n")
elif (self.head == -1):
self.head = 0
self.tail = 0
self.queue[self.tail] = data
else:
self.tail = self.tail + 1
self.queue[self.tail] = data
# Delete an element from the queue
def dequeue(self):
if (self.head == -1):
print("The queue is empty\n")
elif (self.head == self.tail):
temp = self.queue[self.head]
self.head = -1
self.tail = -1
return temp
else:
temp = self.queue[self.head]
self.head = self.head + 1
return temp
def printQueue(self):
if(self.head == -1):
print("No element in the queue")
else:
for i in range(self.head, self.tail + 1):
print(self.queue[i], end=" ")
print()
# Your Queue object will be instantiated and called as such:
obj = Queue(5)
obj.enqueue(1)
obj.enqueue(2)
obj.enqueue(3)
obj.enqueue(4)
obj.enqueue(5)
print("Initial queue")
obj.printQueue()
obj.dequeue()
print("After removing an element from the queue")
obj.printQueue()
// Queue implementation in Java
public class Queue {
int SIZE = 5;
int items[] = new int[SIZE];
int front, rear;
Queue() {
front = -1;
rear = -1;
}
boolean isFull() {
if (rear == SIZE - 1) {
return true;
}
return false;
}
boolean isEmpty() {
if (front == -1)
return true;
else
return false;
}
void enQueue(int element) {
if (isFull()) {
System.out.println("Queue is full");
} else {
if (front == -1)
front = 0;
rear++;
items[rear] = element;
System.out.println("Inserted " + element);
}
}
int deQueue() {
int element;
if (isEmpty()) {
System.out.println("Queue is empty");
return (-1);
} else {
element = items[front];
if (front >= rear) {
front = -1;
rear = -1;
} /* Q has only one element, so we reset the queue after deleting it. */
else {
front++;
}
System.out.println("Deleted -> " + element);
return (element);
}
}
void display() {
/* Function to display elements of Queue */
int i;
if (isEmpty()) {
System.out.println("Empty Queue");
} else {
System.out.println("\nFront index-> " + front);
System.out.println("Items -> ");
for (i = front; i <= rear; i++)
System.out.print(items[i] + " ");
System.out.println("\nRear index-> " + rear);
}
}
public static void main(String[] args) {
Queue q = new Queue();
// deQueue is not possible on empty queue
q.deQueue();
// enQueue 5 elements
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
q.enQueue(4);
q.enQueue(5);
// 6th element can't be added to because the queue is full
q.enQueue(6);
q.display();
// deQueue removes element entered first i.e. 1
q.deQueue();
// Now we have just 4 elements
q.display();
}
}// Queue implementation in C
#include <stdio.h>
#define SIZE 5
void enQueue(int);
void deQueue();
void display();
int items[SIZE], front = -1, rear = -1;
int main() {
//deQueue is not possible on empty queue
deQueue();
//enQueue 5 elements
enQueue(1);
enQueue(2);
enQueue(3);
enQueue(4);
enQueue(5);
// 6th element can't be added to because the queue is full
enQueue(6);
display();
//deQueue removes element entered first i.e. 1
deQueue();
//Now we have just 4 elements
display();
return 0;
}
void enQueue(int value) {
if (rear == SIZE - 1)
printf("\nQueue is Full!!");
else {
if (front == -1)
front = 0;
rear++;
items[rear] = value;
printf("\nInserted -> %d", value);
}
}
void deQueue() {
if (front == -1)
printf("\nQueue is Empty!!");
else {
printf("\nDeleted : %d", items[front]);
front++;
if (front > rear)
front = rear = -1;
}
}
// Function to print the queue
void display() {
if (rear == -1)
printf("\nQueue is Empty!!!");
else {
int i;
printf("\nQueue elements are:\n");
for (i = front; i <= rear; i++)
printf("%d ", items[i]);
}
printf("\n");
}// Queue implementation in C++
#include <iostream>
#define SIZE 5
using namespace std;
class Queue {
private:
int items[SIZE], front, rear;
public:
Queue() {
front = -1;
rear = -1;
}
bool isFull() {
if (rear == SIZE - 1) {
return true;
}
return false;
}
bool isEmpty() {
if (front == -1)
return true;
else
return false;
}
void enQueue(int element) {
if (isFull()) {
cout << "Queue is full";
} else {
if (front == -1) front = 0;
rear++;
items[rear] = element;
cout << endl
<< "Inserted " << element << endl;
}
}
int deQueue() {
int element;
if (isEmpty()) {
cout << "Queue is empty" << endl;
return (-1);
} else {
element = items[front];
if (front >= rear) {
front = -1;
rear = -1;
} /* Q has only one element, so we reset the queue after deleting it. */
else {
front++;
}
cout << endl
<< "Deleted -> " << element << endl;
return (element);
}
}
void display() {
/* Function to display elements of Queue */
int i;
if (isEmpty()) {
cout << endl
<< "Empty Queue" << endl;
} else {
cout << endl
<< "Front index-> " << front;
cout << endl
<< "Items -> ";
for (i = front; i <= rear; i++)
cout << items[i] << " ";
cout << endl
<< "Rear index-> " << rear << endl;
}
}
};
int main() {
Queue q;
//deQueue is not possible on empty queue
q.deQueue();
//enQueue 5 elements
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
q.enQueue(4);
q.enQueue(5);
// 6th element can't be added to because the queue is full
q.enQueue(6);
q.display();
//deQueue removes element entered first i.e. 1
q.deQueue();
//Now we have just 4 elements
q.display();
return 0;
}队列的局限性
正如您在下图所示，经过一番入队和出队操作后，队列的大小减小了。
并且只有在队列被重置（所有元素都已出队）后，我们才能添加索引 0 和 1。
在 REAR 到达最后一个索引后，如果我们能在空出的空间（0 和 1）中存储额外的元素，我们就可以利用这些空的空间。这通过一种称为循环队列的修改队列来实现。
复杂度分析
使用数组实现队列的入队和出队操作的复杂度为O(1)。如果您在 Python 代码中使用pop(N)，则复杂度可能为O(n)，具体取决于要弹出项的位置。
队列的应用
- CPU 调度、磁盘调度
- 当数据在两个进程之间异步传输时。队列用于同步。例如：IO 缓冲区、管道、文件 IO 等
- 实时系统中中断的处理。
- 呼叫中心的电话系统使用队列按顺序等待来电者。