Data Structures Algorithms 简明教程

Queue Data Structure

What is a Queue?

queue 是一个线性数据结构，其中元素按 FIFO（先进先出）原则存储，其中第一个插入的元素将是第一个被访问的元素。队列是一种与堆栈类似的抽象数据类型 (ADT)，队列与堆栈的不同之处在于队列在其两端都是开放的。数据通过一端插入队列，并从另一端删除数据。队列在大多数编程语言中都非常常用。

A queue is a linear data structure where elements are stored in the FIFO (First In First Out) principle where the first element inserted would be the first element to be accessed. A queue is an Abstract Data Type (ADT) similar to stack, the thing that makes queue different from stack is that a queue is open at both its ends. The data is inserted into the queue through one end and deleted from it using the other end. Queue is very frequently used in most programming languages.

car

队列的实际示例可以是单车道单行道，其中的车辆先进入，先退出。更多实际示例可以看作是售票窗口和公共汽车站的队列。

A real-world example of queue can be a single-lane one-way road, where the vehicle enters first, exits first. More real-world examples can be seen as queues at the ticket windows and bus-stops.

Representation of Queues

类似于堆栈 ADT，队列 ADT 也可以使用数组、链表或指针实现。作为本教程中的一个小示例，我们使用一维数组实现队列。

Similar to the stack ADT, a queue ADT can also be implemented using arrays, linked lists, or pointers. As a small example in this tutorial, we implement queues using a one-dimensional array.

Representation of queues

Basic Operations in Queue

队列操作还包括队列的初始化、使用和永久从内存中删除数据。

Queue operations also include initialization of a queue, usage and permanently deleting the data from the memory.

队列 ADT 中最基本的操作包括：enqueue()、dequeue()、peek()、isFull()、isEmpty()。这些都是内置操作，用于执行数据操作和检查队列的状态。

The most fundamental operations in the queue ADT include: enqueue(), dequeue(), peek(), isFull(), isEmpty(). These are all built-in operations to carry out data manipulation and to check the status of the queue.

队列使用两个指针： front 和 rear 。前指针从前端访问数据（帮助入队），而后指针从后端访问数据（帮助出队）。

Queue uses two pointers − front and rear. The front pointer accesses the data from the front end (helping in enqueueing) while the rear pointer accesses data from the rear end (helping in dequeuing).

Queue Insertion Operation: Enqueue()

enqueue() 是一种数据操作操作，用于将元素插入堆栈。以下算法以更简单的方式描述了 enqueue() 操作。

The enqueue() is a data manipulation operation that is used to insert elements into the stack. The following algorithm describes the enqueue() operation in a simpler way.

Algorithm

1. START
2. Check if the queue is full.
3. If the queue is full, produce overflow error and exit.
4. If the queue is not full, increment rear pointer to point
   the next empty space.
5. Add data element to the queue location, where the rear
   is pointing.
6. return success.
7. END

Example

以下是该操作在各种编程语言中的实现 −

Following are the implementations of this operation in various programming languages −

Queue Deletion Operation: dequeue()

dequeue() 是一种数据处理操作，用于从堆栈中移除元素。以下算法以一种更简单的方式描述了 dequeue() 操作。

The dequeue() is a data manipulation operation that is used to remove elements from the stack. The following algorithm describes the dequeue() operation in a simpler way.

Algorithm

1. START
2. Check if the queue is empty.
3. If the queue is empty, produce underflow error and exit.
4. If the queue is not empty, access the data where front
   is pointing.
5. Increment front pointer to point to the next available
   data element.
6. Return success.
7. END

Example

以下是该操作在各种编程语言中的实现 −

Following are the implementations of this operation in various programming languages −

Queue - The peek() Operation

peek() 是一种操作，用于检索队列中最前面的元素，而不会删除它。此操作用于在指针的帮助下检查队列的状态。

The peek() is an operation which is used to retrieve the frontmost element in the queue, without deleting it. This operation is used to check the status of the queue with the help of the pointer.

Algorithm

1. START
2. Return the element at the front of the queue
3. END

Example

以下是该操作在各种编程语言中的实现 −

Following are the implementations of this operation in various programming languages −

Queue - The isFull() Operation

isFull() 操作验证堆栈是否已满。

The isFull() operation verifies whether the stack is full.

Algorithm

1. START
2. If the count of queue elements equals the queue size,
   return true
3. Otherwise, return false
4. END

Example

以下是该操作在各种编程语言中的实现 −

Following are the implementations of this operation in various programming languages −

Queue - The isEmpty() operation

isEmpty() 操作验证堆栈是否为空。此操作用于在顶部指针的帮助下检查堆栈的状态。

The isEmpty() operation verifies whether the stack is empty. This operation is used to check the status of the stack with the help of top pointer.

Algorithm

1. START
2. If the count of queue elements equals zero, return true
3. Otherwise, return false
4. END

Example

以下是该操作在各种编程语言中的实现 −

Following are the implementations of this operation in various programming languages −

Queue Complete Implementation

以下是队列在各种编程语言中的完整实现 −

Following are the complete implementations of Queue in various programming languages −

Queue Implementation in C

单击以查看 Queue Program using C 的实现

Click to check the implementation of Queue Program using C