数据结构 - 用顺序存储方式实现循环队列的 6 种情况 (C++)

用顺序存储方式实现循环队列的 6 种情况(可运行)

王道书提到的 线性队列 实现的 6 种情况,其对应代码实现如下。
为增加可读性使用 ANSI 代码设置输出文本颜色,Windows 系统建议使用 powershell 运行。

// test.cpp
// 编译运行命令 g++ test.cpp -otest ; ./test
#include <iostream>
using namespace std;
#define MaxSize 10
#define ElemType int
// 队尾指针Q.rear的位置:
//   (a)指向表尾的后一位   (b)指向表尾
// 判断队满队空的三种方法:
//   1. 牺牲存储单元(常见)  2.引入size变量   3.引入tag变量(true表示入队,false表示出队)

//a1
struct a1 { ElemType data[MaxSize]; int front, rear; };
void InitQueue(a1 &Q) { Q.front = Q.rear = 0; }
bool EnQueue(a1 &Q, ElemType x) { if ((Q.rear + 1) % MaxSize == Q.front) return false; Q.data[Q.rear] = x; Q.rear = (Q.rear + 1) % MaxSize; return true; }
bool DeQueue(a1 &Q, ElemType &x) { if (Q.front == Q.rear) return false; x = Q.data[Q.front]; Q.front = (Q.front + 1) % MaxSize; return true; }
//a2
struct a2 { ElemType data[MaxSize]; int front, rear, size; };
void InitQueue(a2 &Q) { Q.front = Q.rear = Q.size = 0; }
bool EnQueue(a2 &Q, ElemType x) { if (Q.size == MaxSize) return false; Q.data[Q.rear] = x; Q.rear = (Q.rear + 1) % MaxSize; Q.size++; return true; }
bool DeQueue(a2 &Q, ElemType &x) { if (Q.size == 0) return false; x = Q.data[Q.front]; Q.front = (Q.front + 1) % MaxSize; Q.size--; return true; }
//a3
struct a3 { ElemType data[MaxSize]; int front, rear; bool tag; };
void InitQueue(a3 &Q) { Q.front = Q.rear = 0; Q.tag = false; }
bool EnQueue(a3 &Q, ElemType x) { if (Q.front == Q.rear && Q.tag) return false; Q.data[Q.rear] = x; Q.rear = (Q.rear + 1) % MaxSize; Q.tag = true; return true; }
bool DeQueue(a3 &Q, ElemType &x) { if (Q.front == Q.rear && !Q.tag) return false; x = Q.data[Q.front]; Q.front = (Q.front + 1) % MaxSize; Q.tag = false; return true; }
//b1
struct b1 { ElemType data[MaxSize]; int front, rear; };
void InitQueue(b1 &Q) { Q.front = 0; Q.rear = MaxSize - 1; }
bool EnQueue(b1 &Q, ElemType x) { if ((Q.rear + 2) % MaxSize == Q.front) return false; Q.rear = (Q.rear + 1) % MaxSize; Q.data[Q.rear] = x; return true;}
bool DeQueue(b1 &Q, ElemType &x) { if ((Q.rear + 1) % MaxSize == Q.front) return false; x = Q.data[Q.front]; Q.front = (Q.front + 1) % MaxSize; return true;}
//b2
struct b2 { ElemType data[MaxSize]; int front, rear, size; };
void InitQueue(b2 &Q) { Q.front = Q.size = 0; Q.rear = MaxSize - 1; }
bool EnQueue(b2 &Q, ElemType x) { if (Q.size == MaxSize) return false; Q.rear = (Q.rear + 1) % MaxSize; Q.data[Q.rear] = x; Q.size++; return true; }
bool DeQueue(b2 &Q, ElemType &x) { if (Q.size == 0) return false; x = Q.data[Q.front]; Q.front = (Q.front + 1) % MaxSize; Q.size--; return true; }
//b3
struct b3 { ElemType data[MaxSize]; int front, rear; bool tag; };
void InitQueue(b3 &Q) { Q.front = 0; Q.rear = -1; Q.tag = false; }
bool EnQueue(b3 &Q, ElemType x) { if ((Q.rear + 1) % MaxSize == Q.front && Q.tag) return false; Q.rear = (Q.rear + 1) % MaxSize; Q.data[Q.rear] = x; Q.tag = true; return true; }
bool DeQueue(b3 &Q, ElemType &x) { if ((Q.rear + 1) % MaxSize == Q.front && !Q.tag) return false; x = Q.data[Q.front]; Q.front = (Q.front + 1) % MaxSize; Q.tag = false; return true; }

void PrintQueue(a1 &Q) { cout << "a1 "; for (int i = Q.front; i < (Q.rear - Q.front) % MaxSize; i++) printf("\e[33m%d\e[0m|", Q.data[i % MaxSize]); cout << endl; }
void PrintQueue(a2 &Q) { cout << "a2 "; for (int i = Q.front; i < Q.size; i++) printf("\e[33m%d\e[0m|", Q.data[i % MaxSize]); cout << endl; }
void PrintQueue(a3 &Q) { int size = ((Q.rear - Q.front + 1) % MaxSize && Q.tag) ? MaxSize : (Q.rear - Q.front) % MaxSize; cout << "a3 "; for (int i = Q.front; i < size; i++) printf("\e[33m%d\e[0m|", Q.data[i % MaxSize]); cout << endl; }
void PrintQueue(b1 &Q) { cout << "b1 "; for (int i = Q.front; i < (Q.rear - Q.front + 1) % MaxSize; i++) printf("\e[33m%d\e[0m|", Q.data[i % MaxSize]); cout << endl; }
void PrintQueue(b2 &Q) { cout << "b2 "; for (int i = Q.front; i < Q.size; i++) printf("\e[33m%d\e[0m|", Q.data[i % MaxSize]); cout << endl; }
void PrintQueue(b3 &Q) { int size = ((Q.rear - Q.front) % MaxSize && Q.tag) ? MaxSize : (Q.rear - Q.front) % MaxSize; cout << "b3 "; for (int i = Q.front; i < size; i++) printf("\e[33m%d\e[0m|", Q.data[i % MaxSize]); cout << endl; }

void testQueue() {
    printf("执行\e[32m线性队列\e[0m测试\n");
    a1 a1; a2 a2; a3 a3; b1 b1; b2 b2; b3 b3;
    InitQueue(a1); InitQueue(a2); InitQueue(a3); InitQueue(b1); InitQueue(b2); InitQueue(b3);
    ///////////////////////
    // 此处修改测试代码

    for (int i = 0; i < MaxSize; i++) { EnQueue(a1, i + 1); EnQueue(a2, i + 1); EnQueue(a3, i + 1); EnQueue(b1, i + 1); EnQueue(b2, i + 1); EnQueue(b3, i + 1); }
    if (!EnQueue(a1, 15)) printf("队列已满,入队失败 \n");
    PrintQueue(a1); PrintQueue(a2); PrintQueue(a3); PrintQueue(b1); PrintQueue(b2); PrintQueue(b3);
    ElemType res = 0;
    for (int i = 0; i < MaxSize -2; i++) { DeQueue(a1, res); DeQueue(a2, res); DeQueue(a3, res); DeQueue(b1, res); DeQueue(b2, res); DeQueue(b3, res); }
    for (int i = 0; i < 3; i++) if (!DeQueue(a2, res)) printf("队列已空,出队失败 ");
    PrintQueue(a1); PrintQueue(a2); PrintQueue(a3); PrintQueue(b1); PrintQueue(b2); PrintQueue(b3);

    ///////////////////////
    
}

int main(int argc, char const *argv[])
{
    testQueue();
    cout << endl;
    return 0;
}

@echo off
chcp 65001 > nul
@REM 文件名run.bat,运行程序的简易批处理脚本
(g++ test.cpp -otest ) && (
    echo 编译完成 正在执行
    echo +++++++++++++++++++++
    (test) && (
        echo.
        echo +++++++++++++++++++++
        echo 执行完成
    ) ||(
        echo.
        echo ---------------------
        echo 程序执行出错)
) || (echo 编译出错)
pause

数据结构 - 用顺序存储方式实现循环队列的 6 种情况 (C++)

上一篇:R-Modeling(step 4)


下一篇:C语言 函数缺省参数 - C语言零基础入门教程