用顺序存储方式实现循环队列的 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