注册    登录
今天看啥  ›  专栏  ›  清风烈酒2157

06--队列

清风烈酒2157  · 简书  ·  · 2020-12-15 08:35

[toc]

队列

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

顺序队列

顺序队列 结构必须为其 静态分配 或 动态 申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front，它指向队头元素；另一个是队尾指针rear，它指向下一个入队元素的存储位置，如图所示

5906cf9f961d502bd5e12b4d7f27e7f6

每次在队尾插入一个元素是， rear 增 1 ；每次在队头删除一个元素时， front 增 1 。随着插入和删除操作的进行，队列元素的个数不断变化，队列所占的存储空间也在为队列结构所分配的连续空间中移动。当 front=rear 时，队列中没有任何元素，称为 空队列 。当 rear 增加到指向分配的连续空间之外时，队列无法再插入新元素，但这时往往还有大量可用空间未被占用，这些空间是已经出队的队列元素曾经占用过得存储单元。

  • 顺序队列中的溢出现象：
    • "下溢"现象：当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
    • "真上溢"现象：当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
    • "假上溢"现象：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。

循环队列

在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论 插入 或 删除 ，一旦 rear 指针增 1 或 front 指针增 1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。自己真从 MaxSize-1 增 1 变到 0 ，可用取余运算 rear%MaxSize 和 front%MaxSize 来实现。这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。除了一些简单应用之外，真正实用的队列是循环队列。

f625f32b40801c86a9bf9f44fb50a308

在循环队列中，当队列为空时，有 front=rear ，而当所有队列空间全占满时，也有 front=rear 。为了区别这两种情况，规定循环队列最多只能有 MaxSize-1 个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件时 front=rear ，而队列判满的条件时 front=（rear+1）%MaxSize 。队空和队满的情况如图

50c9687a49abb1a10951c11166a998b9

循环队列顺序存储

取模运算 才能有循环的感觉

初始化 宏定义 

#include "SqStack.h"
typedef struct CircularQueue{
    YZSElemType *data; //存储内存分配基地址
    int front;      //队列头索引
    int rear;       //队列尾索引
}CircularQueue;
//typedef struct CircularQueue * CQueue;
YZStatus InitCQuene(CircularQueue *Q);
YZStatus ClearQueue(CircularQueue *Q);
YZStatus IsEmptyQueue(CircularQueue Q);
YZStatus GetQueueLegth(CircularQueue Q,int *Length);
YZStatus GetTopQuene(CircularQueue Q,YZSElemType *e);
YZStatus PushQuene(CircularQueue *Q,YZSElemType e);
YZStatus PopQuene(CircularQueue *Q,YZSElemType *e);
YZStatus QueueTraverse(CircularQueue Q);

//1.1 初始化
YZStatus InitCQuene(CircularQueue *Q){
    Q->data = malloc(sizeof(YZSElemType)*MAXSIZE);
    if ( Q->data == NULL ) return ERROR;
    Q->front = 0;
    Q->rear = 0;
 
    return OK;
}
清空 
//1.2 清空
YZStatus ClearQueue(CircularQueue *Q){
    Q->front = Q->rear = 0;
    return OK;;
}
是否为空 
//1.3 是否为空
YZStatus IsEmptyQueue(CircularQueue Q){
    if(Q.front == Q.rear) return TRUE;
    return FALSE;
}
长度 
//1.4 长度
YZStatus GetQueueLegth(CircularQueue Q,int *Length){
     if(Q.front == Q.rear) return 0;
    // 算出栈顶 栈尾之间的差值 就是未用的空间
     *Length = (Q.rear-Q.front+MAXSIZE) % MAXSIZE;
     return OK;
}
队列顶部元素 
//1.5 获取队列front元素
YZStatus GetTopQuene(CircularQueue Q,YZSElemType *e){
    if(Q.front == Q.rear) return ERROR;
    *e = Q.data[Q.front];
    return OK;
}
入队 
YZStatus PushQuene(CircularQueue *Q,YZSElemType e){
      if(((Q->rear+1)%MAXSIZE) == Q->front) return ERROR;
       Q->data[Q->rear] = e;
       Q->rear = (Q->rear+1)%MAXSIZE;
       return OK;
}
出队 
//1.7出队列
YZStatus PopQuene(CircularQueue *Q,YZSElemType *e){
      if(Q->front == Q->rear) return ERROR;
       *e = Q->data[Q->front];
       Q->front = (Q->front+1)%MAXSIZE;
       return OK;
}
遍历 
YZStatus QueueTraverse(CircularQueue Q){
    if(Q.front == Q.rear) return ERROR;
     int I;
    i = Q.front;
    while (i != Q.rear) {
        printf("%d   ",Q.data[I]);
        i = (i+1)%MAXSIZE;
    }
    printf("\n");
    return OK;
    
}

循环队列链式存储

e089d9da4099a152ff7c745b8efe899d

出队列,首节点指向首元节点下一个节点,是否首节点下一个节点
入队列,尾插法

初始化 宏定义

一些头文件 宏定义 结构体构造 

#include "stdlib.h"
#include "math.h"
#include "time.h"
#include <stdbool.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int YZStatus;
typedef int YZSElemType; /* SElemType类型根据实际情况而定，这里假设为int */
typedef struct QNode{
   YZSElemType data;
   struct QNode * next;
   
}QNode,*LinkQNode;
typedef struct LinkQueue{
   LinkQNode front;
   LinkQNode rear;
   
}LinkQueue;
YZStatus InitLinkQueue(LinkQueue *Q);
YZStatus DestoryLinkQueue(LinkQueue *Q);
YZStatus ClearLinkQueue(LinkQueue *Q);
YZStatus isEmptyLinkQueue(LinkQueue Q);
int ReturnLengthLinkQueue(LinkQueue Q);
YZStatus EnQueue(LinkQueue *Q,YZSElemType e);
YZStatus DeQueue(LinkQueue *Q,YZSElemType *e);
YZStatus GetHeadQueue(LinkQueue Q,YZSElemType *e);
YZStatus TraverseQueue(LinkQueue Q);

初始化 

YZStatus InitLinkQueue(LinkQueue *Q){
    
    Q->front = Q->rear =    (LinkQNode)malloc(sizeof(QNode));
    if(Q->front == NULL) return ERROR;
    Q->front->next = NULL;
    return OK;
}
销毁 
YZStatus DestoryLinkQueue(LinkQueue *Q){
    
    while (Q->front) {
        Q->rear = Q->front->next;
        free(Q->front);
        Q->front = Q->rear;
    }
    return OK;
  
}
清空 
YZStatus ClearLinkQueue(LinkQueue *Q){
    LinkQNode q,p;
    Q->rear = Q->front;
    q = Q->front->next;
    //头尾在一块指向空
    Q->front->next = NULL;
    
    while (q) {
        p = q->next;
        free(q);
        q = p;
    }
    return OK;
  
}
判空 
YZStatus isEmptyLinkQueue(LinkQueue Q){
    if(Q.rear == Q.front){
        return TRUE;
    }
    return FALSE;
  
}
队列长度 
int ReturnLengthLinkQueue(LinkQueue Q){
    LinkQNode q;
    q = Q.front;//从头结点开始
    int I=0;
    while (q != Q.rear) {
        I++;
        q = q->next;
    }
    return I;
}
入队 
YZStatus EnQueue(LinkQueue *Q,YZSElemType e){
  
    LinkQNode temp = (LinkQNode)malloc(sizeof(QNode));
    if (!temp){return ERROR;}
    temp->data = e;
    temp->next = NULL;
    Q->rear->next = temp;
    Q->rear = temp;
    return OK;
}
出队 
YZStatus DeQueue(LinkQueue *Q,YZSElemType *e){
    if (Q->rear == Q->front) {
        return ERROR;
    }
    LinkQNode q;
    q = Q->front->next;
    Q->front->next = q->next;
    *e = q->data;
    //队尾
    if(q==Q->rear){
        
        Q->rear = Q->front;
        
    }
    free(q);
    
    return OK;
}
遍历 

YZStatus TraverseQueue(LinkQueue Q){
    LinkQNode q;
    q = Q.front->next;//从头结点开始
   
    while (q) {
        printf("%d\n",q->data);
        q = q->next;
    }
    return OK;

}
队列头 
YZStatus GetHeadQueue(LinkQueue Q,YZSElemType *e){
    if (Q.rear == Q.front) {
        return ERROR;
    }
    LinkQNode q;
     q  = Q.front->next;//从头结点开始
    *e = q->data;
    return OK;
}

示例 

LinkQueue Q;
    InitLinkQueue(&Q);
    for (int i=1; i<=10; i++) {
        EnQueue(&Q, i);
    }
     printf("\n");
    TraverseQueue(Q);
    int e;
    GetHeadQueue(Q, &e);
    printf("队列顶%d\n",e);
    DeQueue(&Q, &e);
    printf("出队%d\n",e);

打印 

1
2
3
4
5
6
7
8
9
10
队列顶1
出队1



原文地址：访问原文地址
快照地址： 访问文章快照
推荐文章
中国中铁  ·  向海图强！我国新一代自升式海上风电安装平台交付
16 小时前
中国铁建  ·  杭温高铁正式启动全线联调联试
昨天
中国城市规划  ·  要闻 | 住房城乡建设部召开全国城镇老旧小区改造工作现场会
3 天前
中铁国际集团  ·  毕彦春拜会津巴布韦总统埃默森·姆南加古瓦并开展系列商务活动
4 天前
中国中铁  ·  中国中铁各单位掀起党纪学习教育热潮③
5 天前
浙商杂志  ·  张勇第2棒！丁列明21棒！王水福45棒！李东辉94棒！今天，十位浙商“薪火”相传......
8 月前
高工LED  ·  InfoComm China 2023|利亚德、强力巨彩、京东方等LED显示厂商“众生相”
10 月前
小白读财经  ·  普通人一辈子存钱的天花板是多少？
1 年前
远川出海研究  ·  SHEIN：力压亚马逊的中国隐形冠军
2 年前
学习大国  ·  习近平：建设让党中央放心让人民群众满意的模范机关
4 年前
关于   移动版   ·   Py中国   ·   RSS之家   ·   codingpro   ·   Code   ·   link之家   ·   卧龙AI搜索   ·   藏经阁   ·   小百科
今天看啥 - 微信公众号rss订阅, 微信rss, 稳定的RSS源
© 2024 ~ 沪ICP备11025650号