Data Structures Algorithms 简明教程

Queue Data Structure

What is a Queue?

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

car

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

Representation of Queues

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

Representation of queues

Basic Operations in Queue

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

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

队列使用两个指针: frontrear 。前指针从前端访问数据(帮助入队),而后指针从后端访问数据(帮助出队)。

Queue Insertion Operation: Enqueue()

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

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

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

Queue Deletion Operation: dequeue()

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

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

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

Queue - The peek() Operation

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

Algorithm

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

Example

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

Queue - The isFull() Operation

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

Algorithm

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

Example

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

Queue - The isEmpty() operation

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

Algorithm

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

Example

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

Queue Complete Implementation

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

Queue Implementation in C

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