0%

数据结构-栈和队列（二）队列

发表于 2021-09-16 更新于 2021-09-17 分类于 C/C++数据结构阅读次数：
本文字数： 7.7k 阅读时长 ≈ 7 分钟

数据结构

栈和队列（二）队列

思维导图

3.2.1 队列的基本概念

1、概念

队列（Queue）是只允许在一端进行插入，在另一端删除的线性表

队列是一种特殊的线性结构，它只允许在队列的首部（head/front）进行删除操作，这称为“出队”，而在队列的尾部（tail/rear）进行插入操作，这称为“入队”。当队列中没有元素时（即head == tail），称为空队列。比如买票，每个排队买票的窗口就是一个队列。在这个队列当中，新来的人总是站在队列的最后面，来得越早的人越靠前，也就是越早能买到票，我们称为“先进先出”（First In First Out, FIFO）原则。🚘

队列是一个有序列表，可以用数组或是链表来实现

在队首删除元素，在队尾插入元素

“先进先出”（FIFO）原则

2、基本操作

队列基本操作

InitQueue(&Q)：初始化队列，构造一个空队列Q。

DestroyQueue(&Q)：销毁队列。销毁并释放队列Q所占用的内存空间。

EnQueue(&Q,x)：入队，若队列Q未满，将x加入，使之成为新的队尾。

DeQueue(&Q,&x)：出队，若队列Q非空，删除队头元素，并用x返回。

GetHead(Q,&x)：读队头元素，若队列Q非空，则将队头元素赋值给x。

其他常用操作：

QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。

3.2.2 顺序队列

1、顺序队列

初始状态（队空状态）: Q.front == Q.rear == 0

进队操作：队不满，先送值到队尾元素，再将队尾指针加1

出队操作：队不空，先去队头元素值，再将队头指针加1

会出现“上溢出”，即“假溢出”

2、循环队列

为了解决顺序队列的“假溢出”,充分利用空间，即把存储队列元素的表从逻辑上视为一个环。

用模运算将存储空间在逻辑上变成了“环状” 。取模运算，即取余运算。两个整数 a,b，a%b == a除以b的余数。

队空状态: Q.front == Q.rear；

队满状态：(Q.rear + 1) % MaxSize == Q.front

进队操作：(Q.rear + 1) % MaxSize

出队操作：(Q.front + 1) % MaxSize

队列个数：(Q.rear - Q.front + MaxSize) % MaxSize

3、区分队空和队满的方式

（1）

牺牲一个存储单元 ，队列已满的条件：队尾指针的再下一个位置是队头，

即(Q.rear+1)%MaxSize == Q.front

（2）

类型中增设表示元素个数的数据成员。

插入成功 size++；

删除成功 size–;

队满条件：size==MaxSize

队空条件：size == 0;

队列元素个数 = size

（3）

类型中增设tag数据成员

每次删除操作成功时，都令tag=0；

每次插入操作成功时，都令tag=1；

队满条件：front==rear && tag == 1

队空条件：front==rear && tag == 0

4、代码实现

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#define MaxSize 10
using namespace std;

typedef struct {
    int data[MaxSize];
    int front, rear; //队头指针和队尾指针
} SqQueue;

/**
 * @description: 初始化队列
 * @param {SqQueue} Q
 * @return {*}
 */
bool InitQueue(SqQueue &Q) {
    Q.front = Q.rear = 0; //初始化队列
}

/**
 * @description: 判断队空
 * @param {SqQueue} Q
 * @return {*}
 */
bool isEmpty(SqQueue Q) {
    return Q.front == Q.rear;
}

/**
 * @description: 判断是否上溢出
 * @param {SqQueue} Q
 * @return {*}
 */
bool isFull(SqQueue Q) {
    //牺牲一个单元来区分队空和队满
    return (Q.rear + 1) % MaxSize == Q.front;
}

/**
 * @description: 入队
 * @param {SqQueue} &Q
 * @param {int} e
 * @return {*}
 */
bool EnQueue(SqQueue &Q, int e) {
    if(isFull(Q))
        return false;
    Q.data[Q.rear] = e; //入队
    Q.rear = (Q.rear + 1) % MaxSize; //队尾指针取模后移
    return true;    
}

/**
 * @description: 出队
 * @param {SqQueue} &Q
 * @param {int} &e
 * @return {*}
 */
bool DeQueue(SqQueue &Q, int &e) {
    if(isEmpty(Q))
        return false;
    e = Q.data[Q.front];    
    Q.front = (Q.front + 1) % MaxSize; //队头指针取模后移
    return true;
}

/**
 * @description: 获取头元素
 * @param {SqQueue} Q
 * @return {*}
 */
int
    GetTop(SqQueue Q)
{
    if(isEmpty(Q))
        return -1;
    return Q.data[Q.front];
}

/**
 * @description: 获取队列长度
 * @param {SqQueue} Q
 * @return {*}
 */
int GetLength(SqQueue Q) {
    if(isEmpty(Q))
        return -1;
    return (Q.rear - Q.front + MaxSize) % MaxSize;
}

/**
 * @description: 显示队列
 * @param {SqQueue} Q
 * @return {*}
 */
void printQueue(SqQueue Q)
{
    int t = Q.front;
    int len = t + GetLength(Q);

    for (int i = t; i < len; i++)
    {
        cout << "queue[" << i % MaxSize << "] = " << Q.data[i % MaxSize] << endl;
    }
}
int main() {
    SqQueue Q;
    InitQueue(Q);
    bool loop = true;
    while (loop)
    {
        system("pause");
        system("cls");
        cout << "欢迎进行队列的操作，请按指定序号操作，考研顺利！" << endl;
        cout << "---------------------菜单---------------------" << endl;
        cout << "1、入队" << endl;
        cout << "2、出队" << endl;
        cout << "3、输出队" << endl;
        cout << "4、查看队头元素" << endl;
        cout << "5、查看队长" << endl;
        cout << "0、退出" << endl;
        int num;
        cout << "请选择序号：";
        cin >> num;
        switch (num)
        {
        case 1:
            if (isFull(Q))
            {
                cout << "队满" << endl;
            }
            else
            {
                int e;
                cout << "请输入数据：";
                cin >> e;
                EnQueue(Q, e);
            }

            break;
        case 2:
            if (isEmpty(Q))
            {
                cout << "队空" << endl;
            }
            else
            {
                int e = -1;
                DeQueue(Q, e);
                cout << "出队的数据为：" << e << endl;
            }
            break;
        case 3:
            if (isEmpty(Q))
                cout << "队空" << endl;
            else
                printQueue(Q);
            break;
        case 4:
            if (isEmpty(Q))
            {
                cout << "队空" << endl;
            }
            else
            {
                cout << "队顶的数据为： " << GetTop(Q) << endl;
            }
            break;
        case 5:
            cout << "队长为：" << GetLength(Q) << endl;
            break;
        case 0:
            loop = false;
            break;
        case 6:

            break;
        default:
            break;
        }
    }
    return 0;
}

5、效果实现

3.2.3 链式队列

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#define MaxSize 10
using namespace std;

typedef struct LinkNode 
{
    int data;;
    LinkNode *next;
} LinkNode;

typedef struct {   //链接队列
    int size;
    LinkNode *front, *rear; //队头指针和队尾指针
}LinkQueue;

/**
 * @description: 初始化队列
 * @param {LinkQueue} Q
 * @return {*}
 */
bool InitQueue(LinkQueue &Q)
{
    Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode)); //建立头结点
    Q.front->next = NULL;
    Q.size = 0;
    return true;
}

/**
 * @description: 判断队空
 * @param {LinkQueue} Q
 * @return {*}
 */
bool isEmpty(LinkQueue Q)
{
    // return Q.front == Q.rear;
    return Q.size == 0;
}

/**
 * @description: 入队
 * @param {LinkQueue} &Q
 * @param {int} e
 * @return {*}
 */
bool EnQueue(LinkQueue &Q, int e)
{
    LinkNode *t;
    t = (LinkNode *)malloc(sizeof(LinkNode));
    t->data = e;
    t->next = NULL;
    Q.rear->next = t; //入队
    Q.rear = t;  //队尾指针后移
    Q.size++;
    return true;
}

/**
 * @description: 出队
 * @param {LinkQueue} &Q
 * @param {int} &e
 * @return {*}
 */
bool DeQueue(LinkQueue &Q, int &e)
{
    if (isEmpty(Q))
        return false;
    LinkNode *p = Q.front->next;    
    e = p->data;
    Q.front->next = p->next;  //队头指针后移
    if(Q.rear == p) 
        Q.rear = Q.front;  //若原队列只有一个结点，删除后变空
    free(p);    
    Q.size--;
    return true;
}

/**
 * @description: 获取头元素
 * @param {LinkQueue} Q
 * @return {*}
 */
int GetTop(LinkQueue Q)
{
    if (isEmpty(Q))
        return -1;
    return Q.front->next->data;
}

/**
 * @description: 获取队列长度
 * @param {LinkQueue} Q
 * @return {*}
 */
int GetLength(LinkQueue Q)
{
    return Q.size;
}

/**
 * @description: 显示队列
 * @param {LinkQueue} Q
 * @return {*}
 */
void printQueue(LinkQueue Q)
{
    LinkNode *t = Q.front->next;
    while (t != NULL)
    {
        cout << t->data << "->";
        t = t->next;
    }
    printf("\n");
}
int main()
{
    LinkQueue Q;
    InitQueue(Q);
    bool loop = true;
    while (loop)
    {
        system("pause");
        system("cls");
        cout << "欢迎进行队列的操作，请按指定序号操作，考研顺利！" << endl;
        cout << "---------------------菜单---------------------" << endl;
        cout << "1、入队" << endl;
        cout << "2、出队" << endl;
        cout << "3、输出队" << endl;
        cout << "4、查看队头元素" << endl;
        cout << "5、查看队长" << endl;
        cout << "0、退出" << endl;
        int num;
        cout << "请选择序号：";
        cin >> num;
        switch (num)
        {
        case 1:
            int e;
            cout << "请输入数据：";
            cin >> e;
            EnQueue(Q, e);
            break;
        case 2:
            if (isEmpty(Q))
            {
                cout << "队空" << endl;
            }
            else
            {
                int e = -1;
                DeQueue(Q, e);
                cout << "出队的数据为：" << e << endl;
            }
            break;
        case 3:
            if (isEmpty(Q))
                cout << "队空" << endl;
            else
                printQueue(Q);
            break;
        case 4:
            if (isEmpty(Q))
            {
                cout << "队空" << endl;
            }
            else
            {
                cout << "队顶的数据为： " << GetTop(Q) << endl;
            }
            break;
        case 5:
            cout << "队长为：" << GetLength(Q) << endl;
            break;
        case 0:
            loop = false;
            break;
        case 6:

            break;
        default:
            break;
        }
    }
    return 0;
}

3.2.4 双端队列

欢迎您扫一扫上面的微信公众号，订阅我的博客！

------ 本文结束感谢您的阅读 ------

本文作者： 北以晨光
本文链接： https://mr00wang.github.io/2021/09/16/Queue1/
版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！