队列Queue是一种抽象的数据结构,有点类似于堆栈,与堆栈不同,队列的两端都是打开的。一端始终用于插入数据(入队),另一端用于删除数据(出队)。队列遵循先进先出方法,即首先访问的数据项将首先被访问。
队列的真可以是单车道单向道路,车辆首先进入,然后首先离开。在售票窗口和公交车站的队列中,可以看到更多实际示例。
链接:https://www.learnfk.comhttps://www.learnfk.com/data-structures-algorithms/dsa-queue.html
来源:LearnFk无涯教程网
现在我们知道在队列中,出于不同的原因访问两端。下面给出的下图试图将队列表示解释为数据结构-
与在堆栈中一样,也可以使用数组,链接列表,指针和结构来实现队列。为了简单起见,我们将使用一维数组实现队列。
队列操作可能涉及初始化或定义队列,利用它,然后从内存中完全擦除它。在这里,我们将尝试了解与队列相关的基本操作-
enqueue() - 将数据添加到队列中。
dequeue() - 从队列中删除数据。
peek() - 将元素获取到队列的最前面而不删除它。
isfull() - 检查队列是否已满。
isempty() - 检查队列是否为空。
首先让我们了解队列的这些函数-
Peek() - 函数有助于查看队列前面的数据。peek()函数的算法如下
begin procedure peek return queue[front] end procedure
用C编程语言实现peek()函数-
int peek() { return queue[front]; }
isfull() - 当我们使用单维数组实现队列时,我们只需检查后指针达到MAXSIZE即可确定队列已满。isfull()函数的算法-
begin procedure isfull if rear equals to MAXSIZE return true else return false endif end procedure
用 C 编程语言实现isfull()函数-
bool isfull() { if(rear == MAXSIZE - 1) return true; else return false; }
isempty() - 函数的算法-
begin procedure isempty if front is less than MIN OR front is greater than rear return true else return false endif end procedure
如果 front 的值小于MIN或0,则表明队列尚未初始化,因此为空。
这是C编程代码-
bool isempty() { if(front < 0 || front > rear) return true; else return false; }
队列维护两个数据指针,分别为 front 和 rear 。因此,它的操作比堆栈的实现相对困难。
应该采取以下步骤将数据排队(插入)到队列中-
步骤1 - 检查队列是否已满。
步骤2 - 如果队列已满,则产生溢出错误并退出。
步骤3 - 如果队列未满,请增加后指针以指向下一个空白空间。
步骤4 - 将数据元素添加到后方指向的队列位置。
步骤5 - 返回成功。
有时,我们还会检查队列是否已初始化,以处理任何无法预料的情况。
procedure enqueue(data) if queue is full return overflow endif rear ← rear + 1 queue[rear] ← data return true end procedure
enqueue()在C编程语言中的实现-
int enqueue(int data) if(isfull()) return 0; rear = rear + 1; queue[rear] = data; return 1; end procedure
从队列访问数据是两个任务的进程-访问 front 所指向的数据并在访问后删除数据。采取以下步骤执行出队操作-
步骤1 - 检查队列是否为空。
步骤2 - 如果队列为空,则产生下溢错误并退出。
步骤3 - 如果队列不为空,请访问 front 所指向的数据。
步骤4 - 递增 front 指针以指向下一个可用数据元素。
步骤5 - 返回成功。
procedure dequeue if queue is empty return underflow end if data = queue[front] front ← front + 1 return true end procedure
用C编程语言实现dequeue()-
int dequeue() { if(isempty()) return 0; int data = queue[front]; front = front + 1; return data; }
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <stdbool.h> #define MAX 6 int intArray[MAX]; int front = 0; int rear = -1; int itemCount = 0; int peek() { return intArray[front]; } bool isEmpty() { return itemCount == 0; } bool isFull() { return itemCount == MAX; } int size() { return itemCount; } void insert(int data) { if(!isFull()) { if(rear == MAX-1) { rear = -1; } intArray[++rear] = data; itemCount++; } } int removeData() { int data = intArray[front++]; if(front == MAX) { front = 0; } itemCount--; return data; } int main() { /* insert 5 items */ insert(3); insert(5); insert(9); insert(1); insert(12); // front : 0 // rear : 4 // ------------------ // index : 0 1 2 3 4 // ------------------ // queue : 3 5 9 1 12 insert(15); // front : 0 // rear : 5 // --------------------- // index : 0 1 2 3 4 5 // --------------------- // queue : 3 5 9 1 12 15 if(isFull()) { printf("Queue is full!\n"); } // remove one item int num = removeData(); printf("Element removed: %d\n",num); // front : 1 // rear : 5 // ------------------- // index : 1 2 3 4 5 // ------------------- // queue : 5 9 1 12 15 // insert more items insert(16); // front : 1 // rear : -1 // ---------------------- // index : 0 1 2 3 4 5 // ---------------------- // queue : 16 5 9 1 12 15 // As queue is full, elements will not be inserted. insert(17); insert(18); // ---------------------- // index : 0 1 2 3 4 5 // ---------------------- // queue : 16 5 9 1 12 15 printf("Element at front: %d\n",peek()); printf("----------------------\n"); printf("index : 5 4 3 2 1 0\n"); printf("----------------------\n"); printf("Queue: "); while(!isEmpty()) { int n = removeData(); printf("%d ",n); } }
Queue is full! Element removed: 3 Element at front: 5 ---------------------- index : 5 4 3 2 1 0 ---------------------- Queue: 5 9 1 12 15 16
祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)
HarmonyOS快速入门与实战 -〔QCon+案例研习社〕