队列(常用数据结构之一)

简介: 队列(常用数据结构之一)

队列

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

一个队列为z=(a1,a2,...,an), 如图

1c7e5ed0bf15f28fb815f14790322b0f.png

那么a1为对头元素,an为队尾元素。最早进入队列的元素也会最早出来,只有当最先进入队列的元素都出来以后,后进入的元素才能退出。

在日常生活中,人们去银行办理业务需要排队,这就类似我们提到的队列。每一个新来办理业务的需要按照机器自动生成的编号等待办理,只有前面的人办理完毕,才能轮到排在后面的人办理业务。新来的人进入排队状态就相当于入队,前面办理完业务离开的就相当于出队。队列有两种存储表示:顺序存储和链式存储。采用顺序存储结构的队列被称为顺序队列,采用链式存储结构的队列称为链式队列。


基本运算

InitQueue()     ——初始化队列
EnQueue()        ——进队列
DeQueue()        ——出队列
IsQueueEmpty()   ——判断队列是否为空
IsQueueFull()    ——判断队列是否已满


顺序队列

由于顺序队列的底层使用的是数组,因此需预先申请一块足够大的内存空间初始化顺序队列。除此之外,为了满足顺序队列中数据从队尾进,队头出且先进先出的要求,我们还需要定义两个指针(top 和 rear)分别用于指向顺序队列中的队头元素和队尾元素。

队列为空时,队头指针front和队尾指针rear都指向下标为0的存储单元,当元素a,b,c,d,e,f,g依次进入队列后,元素a~g分别存放在数组下标为0~6的存储单元中,队头指针front指向元素a,队尾指针指rear向元素g的下一位置。


假溢出

在顺序队中,当尾指针已经到了数组的上界,不能再有入队操作,但其实数组中还有空位置,这就叫“假溢出”。解决假溢出的途径———采用循环队列。

例如在图中队列删除a和b,然后依次插入h、i和j,当插入j后,就会出现队尾指针rear越出数组的下界造成“假溢出”,如图

27306ad1e4f90e4939a26ed9a4ba2e86.png


顺序循环队列

为充分利用向量空间,克服"假溢出"现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。即:循环队列中进行出队、入队操作时,头尾指针仍要加1,朝前移动。只不过当头尾指针指向向量上界(QueueSize-1)时,其加1操作的结果是指向向量的下界0。


队空和队满

在循环队列中,队空和队满时队头front和队尾指针rear同时都会指向同一存储单元,即front==rear,如图所示。

c404e1e23b7d5df3fb7424d2ef21aeb5.png


队空

bdf2ffb8680c7e27ec8f1bca0e70497c.png


队满

如何区分队空和队满呢?有以下两种方法:

(1)增加一个标志位。设标志位为tag,初始时,tag=0;当入队成功,则tag=1;出队成功,tag=0。则判断队空的条件为:front==rear&&tag==0;队满的条件为:front==rear&&tag==1;

(2)少用一个存储单元。队空的判断条件为front==rear;队满的判断条件为front==(rear+1)%QueueSize。队满的状态如图。

1ada4066f4d4bda86d68faa019fa33ad.png


存储结构

#define  MAXQSIZE  5 // 存储空间的初始分配量
typedef struct {
  ElemType *base;
  int front;
  int rear;
  int maxSize;
} SqQueue;


基本运算

初始化

Status InitQueue(SqQueue &Q) {
  //分配存储空间
  Q.base = (ElemType*)malloc(MAXQSIZE * sizeof(ElemType));
  if(!Q.base) exit(OVERFLOW);
  //置Q为空队列
  Q.front = Q.rear = 0;
  Q.maxSize = MAXQSIZE;
  return OK;
}


判队列是否为空

Status QueueEmpty(SqQueue Q) {
  if(Q.rear == Q.front) return TRUE;
  else return FALSE;
}


入队函数

Status EnQueue(SqQueue &Q, ElemType e) {
  if((Q.rear + 1) % MAXQSIZE == Q.front)//队列已满
    return ERROR;
  Q.base[Q.rear] = e;//插入队尾
  Q.rear = (Q.rear + 1) % MAXQSIZE;//尾部指针后移,如果到最后则转到头部
  return OK;
}


出队函数

Status DeQueue(SqQueue &Q, ElemType &e) {
  if(Q.front == Q.rear)   //队列空
      return ERROR;
  //返回队头元素
  e = Q.base[Q.front];    
  //队头指针后移,如到最后转到头部
  Q.front = (Q.front + 1) % MAXQSIZE; 
  return OK;
}


输出循环队列函数

void OutQueue(SqQueue Q) {  
  ElemType e;
  if(QueueEmpty(Q)){
    printf("这是一个空队列!");
  } else {
      while(!QueueEmpty(Q)){
        DeQueue(Q, e);
        printf("%6d", e);
        }
      printf("\n");
  }
}


输出循环队列长度

Status QueueLength(SqQueue Q) {
    return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}


销毁队列

Status ClearQueue(SqQueue Q) {
    ///销毁队列Q,Q不再存在
    if(Q.base)
        free(Q.base);
    Q.base = NULL;
    Q.front = Q.rear = 0;
    return OK;
}


主函数

int main() {  
    SqQueue q;
    int cord; 
    ElemType a;
    printf("第一次使用必须初始化!\n");
    //调用初始化算法
    InitQueue(q); 
    do{
        printf("\n 主菜单 \n");
        printf(" 1 初始化循环队列 ");
        printf(" 2 进队一个元素 ");
        printf(" 3 出队一个元素 ");
        printf(" 4 队列长度 ");
        printf(" 5 销毁队列 ");
        printf(" 6 结束程序运行 ");
        printf("\n------------------------------------------------------------------\n");
        printf("请输入您的选择( 1, 2, 3, 4, 5, 6)");
        scanf("%d", &cord);
        printf("\n");
        switch(cord) {
            case 1:
                InitQueue(q); //调用初始化算法;
                OutQueue(q);
                break;
            case 2:
                printf("请输入要插入的数据元素:a=");
                scanf("%d", &a);
                EnQueue (q, a); //调用进队算法;
                printf("%d 进队之后的队列:",a);
                OutQueue(q);
                break;
            case 3:
                DeQueue (q, a); //调用出队算法;
                printf("队头元素 %d 出队之后的队列:", a);
                OutQueue(q);
                break;
            case 4:
                printf("该队列长度为: %d", QueueLength(q));
                break;
            case 5:
                ClearQueue(q);
                break;
            case 6:
                exit(0);
                }
    } while(cord <= 4);
    return 0;
}


目录
相关文章
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
131 9
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
初步认识栈和队列
初步认识栈和队列
61 10
|
2月前
|
存储 算法 定位技术
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
25 0
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
|
2月前
|
存储 安全 Java
【用Java学习数据结构系列】探索栈和队列的无尽秘密
【用Java学习数据结构系列】探索栈和队列的无尽秘密
33 2
|
2月前
【数据结构】-- 栈和队列
【数据结构】-- 栈和队列
18 0
|
2月前
探索数据结构:队列的的实现与应用
探索数据结构:队列的的实现与应用
|
2月前
|
存储 C语言
栈和队列题目练习
栈和队列题目练习
20 0
|
2月前
|
存储 算法 Java
【用Java学习数据结构系列】用堆实现优先级队列
【用Java学习数据结构系列】用堆实现优先级队列
35 0
|
2月前
|
C语言
数据结构------栈(Stack)和队列(Queue)
数据结构------栈(Stack)和队列(Queue)
21 0