认识达内从这里开始

队列是编程中一种有用的数据结构。类似于电影院外的售票队列，第一个进入队列的人就是第一个拿到票的人。

在编程术语中，将项目放入队列称为enqueue，从队列中移除项目称为dequeue。

我们可以使用任何编程语言(如 C、C++、Java、Python 或 C#)实现队列，但规范几乎相同。

队列的基本操作

队列是一个对象(一种抽象数据结构 - ADT)，它允许以下操作：

Enqueue : 向队列末尾添加一个元素

Dequeue : 从队列前面移除一个元素

IsEmpty : 检查队列是否为空

IsFull : 检查队列是否已满

Peek：获取队列前端的值而不移除它

队列的工作

队列操作的工作方式如下：

两个指针和跟踪队列的第一个元素

跟踪队列的最后一个元素

最初，设置值和-1

入队操作

检查队列是否已满

对于第一个元素，设置值到 0

增加索引 1

在指向的位置添加新元素

出队操作

检查队列是否为空

返回指向的值增加索引 1

对于最后一个元素，重置值和-1

我们通常使用数组来实现 Java 和 C/++ 中的队列。对于 Python，我们使用列表。

// Queue implementation in Javapublic class Queue { int SIZE = 5; int items[] = new int[SIZE]; int front, rear; Queue() { front = -1; rear = -1; } boolean isFull() { if (front == 0 && 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(); }}

复杂性分析

使用数组的队列中入队和出队操作的复杂度为O(1)。如果您pop(N)在 python 代码中使用，那么复杂性可能O(n)取决于要弹出的项目的位置。

队列的应用

CPU调度、磁盘调度

当两个进程之间异步传输数据时，队列用于同步。例如：IO Buffers、管道、文件IO等

处理实时系统中的中断。

呼叫中心电话系统使用队列将呼叫他们的人按顺序排列。

【免责声明】本文系本网编辑部分转载，转载目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与管理员联系，我们会予以更改或删除相关文章，以保证您的权益!更多内容请添加danei0707学习了解。欢迎关注“达内在线”参与分销，赚更多好礼。