[数据结构-6] 详解队列及其两种储存结构的实现_如图所示:当front 和rear被封装在一起作为头节点后,以链接方式存储的队列在进行插

目录

初步认识

几种储存结构

循环顺序储存

链式存储结构

双端队列

C语言实现

顺序存储

链式储存

---

初步认识

同样我们先从数据结构的三要素来初步了解队列:

• 逻辑结构: 线性结构
• 物理(储存)结构: 一般有两种: 顺序结构和链式结构

前两者队列和栈没有任何区别, 主要是操作上的区别

• 操作: 队列只能从一端(对尾)增加元素, 从另一端(队头)减少元素 

就和排队一样, 人们都从一侧开始排, 从另一侧离开, 所以队列的特点是先进先出

几种储存结构

循环顺序储存

指用一个循环数组实现队列, 并用两个指针front和rear分别指向队头和队尾的后一个元素

注意一个问题:

• 当队为空时, front == rear
• 当队为满时, front == (rear + 1) % MaxSize

MaxSize是数组的长度,而队列能储存的元素数量最大只有MaxSize-1, 队头前一个元素的空间不存储数据,用来判断时空队还是满队

链式存储结构

如果你熟悉链表, 这种结构就没有什么好说的了, 无非就是在普通链表的基础上限制了一些操作(默认第一个节点是队头, 最后一个节点是队尾), 如:

• 入队: 尾部增加一个元素
• 出队: 头部删除一个元素

所以适合做队列的链表可以是下面几种:

• 有头指针, 尾指针的非循环单链表/双链表
• 只有尾指针的循环单链表 (循环单链表的尾指针比头指针有用, 懂得都懂)
• 只有头指针或者只有尾指针的循环双链表 (既然两边都循环了, 爱咋地咋地了)

双端队列

双端队列就是两端都能出队和入队的队列, 可以分为以下几种:

• 输入和输出都不受限: 两端都能进行输入和输出

• 输入受限: 只有一端可以输入, 两端都能输出

• 输出受限: 只有一端可以输出, 两端都能输入

C语言实现

顺序存储

/**
 * @file sequence_queue.c
 * @author xiaoxiao (you@domain.com)
 * @brief 循环顺序队列
 * @version 0.1
 * @date 2022-03-07
 * 
 * @copyright Copyright (c) 2022
 * 
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
#define MaxSize 5
 
/**
 * @brief 循环队列
 * front = rear表示空队列
 * front = (rear + 1) % maxSize 表示满队列
 */
typedef struct Queue{
    int front; // 指向队头
    int rear; // 指向队尾的后一个元素
    int* data;
} Queue;
 
typedef Queue* PQueue;
 
/**
 * @brief 初始化一个队列
 * 
 * @return PQueue 指向队列的指针
 */
PQueue initailQueue(){
    PQueue pQueue = (PQueue) malloc (sizeof(PQueue));
    if(pQueue == NULL){
        printf("no more memory for queue");
        exit(1);
    }
    pQueue -> front = 0;
    pQueue -> rear = 0;
    pQueue -> data = (int*) malloc (MaxSize * sizeof(int));   
    if(pQueue -> data == NULL){
        printf("no more memory for data");
        exit(1);
    }
    return pQueue;
}
 
/**
 * @brief 队列是否为空
 * 
 * @param pQueue 队指针
 * @return true 为空
 * @return false 不为空
 */
bool isEmpty(PQueue pQueue){
    return pQueue -> front == pQueue -> rear;
}
 
/**
 * @brief 队列是否已满
 * 
 * @param pQueue 队指针
 * @return true 队已满
 * @return false 队未满
 */
bool isFull(PQueue pQueue){
    return pQueue -> front == (pQueue -> rear + 1) % (MaxSize);
}
 
/**
 * @brief 入队
 * 
 * @param pQueue 队指针 
 * @param data 入队的数据
 * @return true 入队成功
 * @return false 入队失败
 */
bool enQueue(PQueue pQueue, int data){
    if(isFull(pQueue)){
        printf("队列已满,无法入队\n");
        return false;
    }
    pQueue -> data[pQueue -> rear] = data;
    pQueue -> rear = (pQueue -> rear + 1) % MaxSize;
    return true;
}
 
/**
 * @brief 出队
 * 
 * @param pQueue 队指针
 * @return true
 * @return false
 */
int deQueue(PQueue pQueue){
    if(isEmpty(pQueue)){
        printf("队列为空,无法出队\n");
        return -1;
    }
    int data = pQueue -> data[pQueue -> front];
    pQueue -> front = (pQueue -> front + 1) % MaxSize;
    return data;
}
 
void printQueue(PQueue pQueue){
    if(isEmpty(pQueue)){
        printf("队列为空,无法打印\n");
        return;
    }
    printf("打印当前队列: ");
    int rear = pQueue -> rear;
    if(pQueue -> rear < pQueue -> front)
        rear += MaxSize;
    for(int i = pQueue -> front; i < rear; i ++)
        printf("%d ", pQueue -> data[i < MaxSize ? i : i - MaxSize]);
    printf("\n");
}
 
/**
 * @brief 销毁队列
 */
void destoryQueue(PQueue pQueue){
    free(pQueue -> data);
    free(pQueue);
}
 
int main(){
    printf("-----------------\n");
    PQueue pQueue = initailQueue();
    deQueue(pQueue);
    enQueue(pQueue, 2);
    printQueue(pQueue);
    printf("-----------------\n");
    destoryQueue(pQueue);
}

链式储存

这里引用了实现链表的头文件linked_list.hhttps://blog.csdn.net/xiaoyouyouaaa/article/details/123245470?spm=1001.2014.3001.5501​​​​​​​

/**
 * @file linked_queue.c
 * @author xiaoxiao (you@domain.com)
 * @brief 链式队列
 * @version 0.1
 * @date 2022-03-09
 * 
 * @copyright Copyright (c) 2022
 * 
 */
 
#include <stdio.h>
#include "linked_list.h"
 
/**
 * @brief 初始化一个队列
 * 队头就是链表第一个元素
 * 队尾就是链表最后一个元素
 * 
 * @return PNode 链表头(非队头)
 */
PNode initailQueue(){
    return initalList();
}
 
/**
 * @brief 队列是否为空
 * 
 * @param pQueue 队指针
 * @return true 为空
 * @return false 不为空
 */
bool isEmpty(PNode pQueue){
    return pQueue -> next == NULL;
}
 
/**
 * @brief 入队
 * 
 * @param pQueue 队指针 
 * @param data 入队的数据
 * @return true 入队成功
 * @return false 入队失败
 */
void enQueue(PNode pQueue, int data){
    insertInTail(pQueue, data);
}
 
/**
 * @brief 出队
 * 
 * @param pQueue 队指针
 * @return true
 * @return false
 */
bool deQueue(PNode pQueue){
    return deleteTail(pQueue);
}
 
void printQueue(PNode pQueue){
    printList(pQueue);
}
 
/**
 * @brief 销毁队列
 */
void destoryQueue(PNode pQueue){
    destroyList(pQueue);
}
 
int main(){
    printf("-----------------\n");
    PNode pQueue = initailQueue();
    deQueue(pQueue);
    enQueue(pQueue, 2);
    printQueue(pQueue);
    printf("-----------------\n");
    destoryQueue(pQueue);
}