队列Queue是一种抽象的数据结构,有点类似于堆栈,与堆栈不同,队列的两端都是打开的。一端始终用于插入数据(入队),另一端用于删除数据(出队)。队列遵循先进先出方法,即首先访问的数据项将首先被访问。

Queue Example

队列的真可以是单车道单向道路,车辆首先进入,然后首先离开。在售票窗口和公交车站的队列中,可以看到更多实际示例。

链接:https://www.learnfk.comhttps://www.learnfk.com/data-structures-algorithms/dsa-queue.html

来源:LearnFk无涯教程网

队列表示

现在我们知道在队列中,出于不同的原因访问两端。下面给出的下图试图将队列表示解释为数据结构-

Queue Example

与在堆栈中一样,也可以使用数组,链接列表,指针和结构来实现队列。为了简单起见,我们将使用一维数组实现队列。

基本操作

队列操作可能涉及初始化或定义队列,利用它,然后从内存中完全擦除它。在这里,我们将尝试了解与队列相关的基本操作-

  • 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     -   返回成功。

Insert Operation

有时,我们还会检查队列是否已初始化,以处理任何无法预料的情况。

入队操作算法

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   -  返回成功。

Remove Operation

出队操作算法

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;
}

C语言完整程序

#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

祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)

技术教程推荐

全栈工程师修炼指南 -〔熊燚(四火)〕

乔新亮的CTO成长复盘 -〔乔新亮〕

Spring编程常见错误50例 -〔傅健〕

容量保障核心技术与实战 -〔吴骏龙〕

HarmonyOS快速入门与实战 -〔QCon+案例研习社〕

技术领导力实战笔记 2022 -〔TGO 鲲鹏会〕

手把手带你搭建推荐系统 -〔黄鸿波〕

B端体验设计入门课 -〔林远宏(汤圆)〕

结构思考力 · 透过结构看表达 -〔李忠秋〕

好记忆不如烂笔头。留下您的足迹吧 :)