C/C++ 数据结构与算法【栈和队列】 栈+队列详细解析【日常学习，考研必备】带图+详细代码

一、介绍

栈和队列是限定插入和删除只能在表的“端点”进行的线性表，是线性表的子集，是插入和删除位置受限的线性表。

（操作受限的线性表）

二、栈

1）概念：

栈(stack)是一个特殊的线性表，是限仅在一端（通常是表尾）进行插入和删除操作的线性表。

表尾(即an端)称为栈顶Top;
表头(即a1端)称为栈底Base；

插入元素到栈顶（即表尾）的操作，称为入栈。

从栈顶（即表尾）删除最后一个元素的操作，称为出栈。

“入” = 压入 = PUSH(x)“出” = 弹出 = POP(y)

2）特点：先进后出

3）示意图：

4）常见问题：

数制转换          表达式求值
括号匹配的检验     八皇后问题
行编辑程序         函数调用
迷宫求解          递归调用的实现

5）栈的表示：

1、栈的抽象数据类型的类型定义：

2、相关操作：

6）顺序栈的表示和实现：

1、存储方式：

同一般线性表的顺序存储结构完全相同，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。栈底一般在低地址端。

• 附设top指针，指示栈顶元素在顺序栈中的位置。
• 另设base指针，指示栈底元素在顺序栈中的位置。

但是，为了方便操作，通常top 指示真正的栈顶元素之上的下标地址

• 另外，用stacksize表示栈可使用的最大容量。
  
  

2、栈空标志：

base == top 是栈空标志

3、栈满标志：

top - base == stacksize

4、栈满处理方法：

1. 报错返回操作系统。
2. 分配更大的操作空间，作为栈的存储空间，将原有的内容移入新栈。

使用数组作为顺序栈存储方式的特点：简单，方便、但易产生溢出(数组大小固定)

• **上溢(overflow)：**栈已经满，又要压入元素
• **下溢(underflow)：**栈已经空，还要弹出元素

注：上溢是一种错误，使问题的处理无法进行;而下溢一般认为是一种结束条件，即问题处理结束。

5、定义顺序栈结构

#include <iostream>
#include <cstdlib>using namespace std;#define OK 1    //成功标识
#define ERROR 0 //失败标识#define MAXSIZE 100  //存储空间的初始分配量typedef int Status;	//Status是函数的类型，其值是函数结果状态代码，如OK等typedef int SElemType;   //ElemType的类型根据实际情况而定，这里假定为inttypedef struct{SElemType *base; // 栈底指针SElemType *top;  // 栈顶指针int stackSize;   // 栈可用最大容量
}SqStack;

6、顺序栈的初始化

// 顺序栈的初始化
Status InitStack(SqStack* S) {         // 构造一个空栈S->base = new SElemType[MAXSIZE];  // 或S.base = (SElemType*)malloc(MAXSIZE*sizeof(SElemType))if (!S->base) return ERROR;        // 内存分配失败S->top = S->base; // 栈顶指针等于栈底指针S->stackSize = 0; return OK;
}

7、顺序栈的清空与销毁

// 清空栈
Status ClearStack(SqStack *S) {if (S->base) { // 如果存在这个栈S->top = S->base;S->stackSize = 0; // 将栈顶等于栈底就为空 }return OK;
}// 销毁栈
Status DestroyStack(SqStack* S) {if (S->base) {delete[] S->base;S->base = nullptr;S->top = nullptr;S->stackSize = 0;}return OK;
}

8、求顺序栈长度和判断是否为空

// 判断顺序栈是否为空
Status StackEmpty(SqStack S) {//若栈为空，返回TRUE;否则返回FALSEif (S.top == S.base) {return OK;}else {return ERROR;}
}// 求顺序栈长度
int StackLength(SqStack S) {return S.top - S.base;
}

9、顺序栈的入栈

// 入栈操作
Status Push(SqStack* S, SElemType e) {if (S->top - S->base >= MAXSIZE) return ERROR; // 栈满*S->top = e;S->top++;S->stackSize++;return OK;
}

10、顺序栈的出栈

// 出栈操作
Status Pop(SqStack* S, SElemType* e) {if (S->top == S->base) return ERROR; // 栈空S->top--;*e = *S->top;S->stackSize--;return OK;
}

11、获取栈顶元素

// 获取栈顶元素
Status GetTop(SqStack S, SElemType* e) {if (S.top == S.base) return ERROR; // 栈空*e = *(S.top - 1);return OK;
}

12、运行测试

// 打印栈内元素
void PrintStack(SqStack S) {if (S.top == S.base) {cout << "栈为空" << std::endl;return;}cout << "栈内元素: ";for (SElemType* p = S.base; p < S.top; ++p) {cout << *p << " ";}cout << endl;
}int main() {SqStack S;SElemType e;// 初始化栈if (InitStack(&S) == OK) {cout << "栈初始化成功" << endl;}else {cout << "栈初始化失败" << endl;return -1;}// 入栈操作if (Push(&S, 1) == OK && Push(&S, 2) == OK && Push(&S, 3) == OK) {cout << "入栈成功" << endl;PrintStack(S); // 打印栈内元素}else {cout << "入栈失败" << endl;}// 获取栈顶元素if (GetTop(S, &e) == OK) {cout << "栈顶元素: " << e << endl;}else {cout << "栈为空" << endl;}// 出栈操作while (Pop(&S, &e) == OK) {cout << "出栈元素: " << e << std;PrintStack(S); // 打印栈内元素}// 判断栈是否为空if (StackEmpty(S) == OK) {cout << "栈为空" << endl;}else {cout << "栈非空" << endl;}// 获取栈的长度cout << "栈的长度: " << StackLength(S) << endl;// 清空栈if (ClearStack(&S) == OK) {cout << "栈已清空" << endl;}else {cout << "清空栈失败" << endl;}// 销毁栈if (DestroyStack(&S) == OK) {cout << "栈已销毁" << endl;}else {cout << "销毁栈失败" << endl;}return 0;
}

13、总体代码

#include <iostream>
#include <cstdlib>using namespace std;#define OK 1    //成功标识
#define ERROR 0 //失败标识#define MAXSIZE 100  //存储空间的初始分配量typedef int Status;	//Status是函数的类型，其值是函数结果状态代码，如OK等typedef int SElemType;   //ElemType的类型根据实际情况而定，这里假定为inttypedef struct{SElemType *base; // 栈底指针SElemType *top;  // 栈顶指针int stackSize;   // 栈可用最大容量
}SqStack;// 顺序栈的初始化
Status InitStack(SqStack* S) {         // 构造一个空栈S->base = new SElemType[MAXSIZE];  // 或S.base = (SElemType*)malloc(MAXSIZE*sizeof(SElemType))if (!S->base) return ERROR;        // 内存分配失败S->top = S->base; // 栈顶指针等于栈底指针S->stackSize = 0; return OK;
}// 判断顺序栈是否为空
Status StackEmpty(SqStack S) {//若栈为空，返回TRUE;否则返回FALSEif (S.top == S.base) {return OK;}else {return ERROR;}
}// 求顺序栈长度
int StackLength(SqStack S) {return S.top - S.base;
}// 清空栈
Status ClearStack(SqStack *S) {if (S->base) { // 如果存在这个栈S->top = S->base;S->stackSize = 0; // 将栈顶等于栈底就为空 }return OK;
}// 销毁栈
Status DestroyStack(SqStack* S) {if (S->base) {delete[] S->base;S->base = nullptr;S->top = nullptr;S->stackSize = 0;}return OK;
}// 入栈操作
Status Push(SqStack* S, SElemType e) {if (S->top - S->base >= MAXSIZE) return ERROR; // 栈满*S->top = e;S->top++;S->stackSize++;return OK;
}// 出栈操作
Status Pop(SqStack* S, SElemType* e) {if (S->top == S->base) return ERROR; // 栈空S->top--;*e = *S->top;S->stackSize--;return OK;
}// 获取栈顶元素
Status GetTop(SqStack S, SElemType* e) {if (S.top == S.base) return ERROR; // 栈空*e = *(S.top - 1);return OK;
}// 打印栈内元素
void PrintStack(SqStack S) {if (S.top == S.base) {cout << "栈为空" << std::endl;return;}cout << "栈内元素: ";for (SElemType* p = S.base; p < S.top; ++p) {cout << *p << " ";}cout << endl;
}int main() {SqStack S;SElemType e;// 初始化栈if (InitStack(&S) == OK) {cout << "栈初始化成功" << endl;}else {cout << "栈初始化失败" << endl;return -1;}// 入栈操作if (Push(&S, 1) == OK && Push(&S, 2) == OK && Push(&S, 3) == OK) {cout << "入栈成功" << endl;PrintStack(S); // 打印栈内元素}else {cout << "入栈失败" << endl;}// 获取栈顶元素if (GetTop(S, &e) == OK) {cout << "栈顶元素: " << e << endl;}else {cout << "栈为空" << endl;}// 出栈操作while (Pop(&S, &e) == OK) {std::cout << "出栈元素: " << e << std::endl;PrintStack(S); // 打印栈内元素}// 判断栈是否为空if (StackEmpty(S) == OK) {cout << "栈为空" << endl;}else {cout << "栈非空" << endl;}// 获取栈的长度cout << "栈的长度: " << StackLength(S) << endl;// 清空栈if (ClearStack(&S) == OK) {cout << "栈已清空" << endl;}else {cout << "清空栈失败" << endl;}// 销毁栈if (DestroyStack(&S) == OK) {cout << "栈已销毁" << endl;}else {cout << "销毁栈失败" << endl;}return 0;
}

14、运行结果

7）链栈的表示和实现

1、存储方式

链栈是运算受限的单链表，只能正在链表头部进行操作

• 链表的头指针就是栈顶

• 不需要头结点

• 基本不存在栈满的情况

• 空栈相当于头指针指向空

• 插入和删除仅在栈顶处执行

2、定义链栈结构

#include <iostream>
using namespace std;// 函数结果状态码 
#define OK 1    //成功标识
#define ERROR 0 //失败标识#define MAXSIZE 100  //线性表存储空间的初始分配量typedef int Status;	//Status是函数的类型，其值是函数结果状态代码，如OK等typedef int SElemType;   //ElemType的类型根据实际情况而定，这里假定为inttypedef struct StackNode {SElemType data;struct StackNode* next;
}StackNode, *LinkStack;

3、链栈的初始化

// 初始化链栈
Status InitStack(LinkStack& S) {S = NULL;return OK;
}

4、链栈的清空与销毁

// 销毁链栈
void DestroyStack(LinkStack& S) {LinkStack p;while (S != NULL) {p = S;S = S->next;delete p;}
}// 清空链栈
void ClearStack(LinkStack& S) {DestroyStack(S);InitStack(S);
}

5、求链栈长度和判断链栈是否为空

// 获取链栈的长度
int StackLength(LinkStack S) {int length = 0;LinkStack p = S;while (p != NULL) {length++;p = p->next;}return length;
}// 判断链栈是否为空
Status StackEmpty(LinkStack S) {if (S == NULL) {return OK;}else {return ERROR;}
}

6、链栈的入栈

// 入栈操作
Status Push(LinkStack& S, SElemType e) {LinkStack p;p = new StackNode; // 生成一个新节点if (p == NULL) return ERROR; // 内存分配失败p->data = e; // 将新节点数据域置为ep->next = S; // 将新节点插入栈顶S = p;       // 修改栈顶指针return OK;
}

7、链栈的出栈

// 出栈操作
Status Pop(LinkStack& S, SElemType& e) {if (S == NULL) return ERROR; // 栈空LinkStack p = S;;e = p->data;S = p->next;delete p;return OK;
}

8、获取栈顶元素

// 获取栈顶元素
Status GetTop(LinkStack& S, SElemType& e) {if (S == NULL) return ERROR; // 栈空e = S->data;return OK;
}

9、运行测试

// 打印链栈内元素
void PrintStack(LinkStack& S) {if (S == NULL) {cout << "栈为空" << endl;return;}cout << "栈内元素: ";LinkStack p = S;while (p != NULL) {cout << p->data << " ";p = p->next;}cout << endl;
}int main() {LinkStack stack;InitStack(stack);int choice, value;bool running = true;while (running) {cout << "1. 入栈\n2. 出栈\n3. 获取栈顶元素\n4. 判断链栈是否为空\n5. 清空链栈\n6. 获取链栈长度\n7. 打印栈内元素\n8. 退出\n";cout << "请输入你的选择: ";cin >> choice;switch (choice) {case 1:cout << "请输入你要入栈的元素: ";cin >> value;if (Push(stack, value) == OK) {cout << "入栈成功" << endl;}else {cout << "入栈失败" << endl;}PrintStack(stack);break;case 2:if (Pop(stack, value) == OK) {cout << "出栈的元素为: " << value << endl;}else {cout << "链栈为空" << endl;}PrintStack(stack);break;case 3:if (GetTop(stack, value) == OK) {cout << "栈顶元素为: " << value << endl;}else {cout << "链栈为空" << endl;}break;case 4:if (StackEmpty(stack) == OK) {cout << "链栈为空" << endl;}else {cout << "链栈不为空" << endl;}break;case 5:ClearStack(stack);cout << "清空链栈" << endl;PrintStack(stack);break;case 6:cout << "链栈的长度为: " << StackLength(stack) << endl;break;case 7:PrintStack(stack);break;case 8:running = false;break;default:cout << "Invalid choice" << endl;break;}}DestroyStack(stack);return 0;
}

10、总体代码

#include <iostream>
using namespace std;// 函数结果状态码 
#define OK 1    //成功标识
#define ERROR 0 //失败标识#define MAXSIZE 100  //线性表存储空间的初始分配量typedef int Status;	//Status是函数的类型，其值是函数结果状态代码，如OK等typedef int SElemType;   //ElemType的类型根据实际情况而定，这里假定为inttypedef struct StackNode {SElemType data;struct StackNode* next;
}StackNode, *LinkStack;// 初始化链栈
Status InitStack(LinkStack& S) {S = NULL;return OK;
}// 销毁链栈
void DestroyStack(LinkStack& S) {LinkStack p;while (S != NULL) {p = S;S = S->next;delete p;}
}// 入栈操作
Status Push(LinkStack& S, SElemType e) {LinkStack p;p = new StackNode; // 生成一个新节点if (p == NULL) return ERROR; // 内存分配失败p->data = e; // 将新节点数据域置为ep->next = S; // 将新节点插入栈顶S = p;       // 修改栈顶指针return OK;
}// 出栈操作
Status Pop(LinkStack& S, SElemType& e) {if (S == NULL) return ERROR; // 栈空LinkStack p = S;;e = p->data;S = p->next;delete p;return OK;
}// 获取栈顶元素
Status GetTop(LinkStack& S, SElemType& e) {if (S == NULL) return ERROR; // 栈空e = S->data;return OK;
}// 判断链栈是否为空
Status StackEmpty(LinkStack S) {if (S == NULL) {return OK;}else {return ERROR;}
}// 清空链栈
void ClearStack(LinkStack& S) {DestroyStack(S);InitStack(S);
}// 获取链栈的长度
int StackLength(LinkStack S) {int length = 0;LinkStack p = S;while (p != NULL) {length++;p = p->next;}return length;
}// 打印链栈内元素
void PrintStack(LinkStack& S) {if (S == NULL) {cout << "栈为空" << endl;return;}cout << "栈内元素: ";LinkStack p = S;while (p != NULL) {cout << p->data << " ";p = p->next;}cout << endl;
}int main() {LinkStack stack;InitStack(stack);int choice, value;bool running = true;while (running) {cout << "1. 入栈\n2. 出栈\n3. 获取栈顶元素\n4. 判断链栈是否为空\n5. 清空链栈\n6. 获取链栈长度\n7. 打印栈内元素\n8. 退出\n";cout << "请输入你的选择: ";cin >> choice;switch (choice) {case 1:cout << "请输入你要入栈的元素: ";cin >> value;if (Push(stack, value) == OK) {cout << "入栈成功" << endl;}else {cout << "入栈失败" << endl;}PrintStack(stack);break;case 2:if (Pop(stack, value) == OK) {cout << "出栈的元素为: " << value << endl;}else {cout << "链栈为空" << endl;}PrintStack(stack);break;case 3:if (GetTop(stack, value) == OK) {cout << "栈顶元素为: " << value << endl;}else {cout << "链栈为空" << endl;}break;case 4:if (StackEmpty(stack) == OK) {cout << "链栈为空" << endl;}else {cout << "链栈不为空" << endl;}break;case 5:ClearStack(stack);cout << "清空链栈" << endl;PrintStack(stack);break;case 6:cout << "链栈的长度为: " << StackLength(stack) << endl;break;case 7:PrintStack(stack);break;case 8:running = false;break;default:cout << "Invalid choice" << endl;break;}}DestroyStack(stack);return 0;
}

11、运行结果

三、栈与递归

1）递归的定义

若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的；

若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。

例如：递归求n的阶乘

long(Facty( long n ) {if(n == 0) return 1;else return n * Fact(n-1);
}

以下三种情况常常用到递归方法：

• 递归定义的数学函数
• 具有递归特性的数据结构
• 可递归求解的问题

2）递归问题——用分治法求解

分治法：对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解

必备的三个条件：

1. 能将一个问题转变成、个新问题，而新问题与原问题的解法相同或类同，不同的仅是处理的对象，且这些处理对象是变化有规律的
2. 可以通过上述转化而使问题简化
3. 必须有一个明确的递归出口，重或称递归的边界

3）分治法求递归问题算法的一般形式

void p (参数表) {if (递归结束条件) 可直接求解步骤;  ——基本项else p (较小的参数);         ——归纳项
}

例如:

long Fact ( long n){if(n == 0) return 1; // 基本项else return n * Fact(n - 1); // 归纳项
}

4）函数调用过程

调用前,系统完成:

(1)将实参,返回地址等传递给被调用函数

(2)为被调用函数的局部变量分配存储区(3)将控制转移到被调用函数的入口

调用后,系统完成:

(1)保存被调用函数的计算结果

(2)释放被调用函数的数据区(3)依照被调用函数保存的返回地址将控制转移到调用函数

当多个函数构成嵌套调用

遵循后调用先返回

例如：

int main(void){...y= fact(3);...
}
double fact(int n) {...Z = mypow(3.5, 2);...
}
double mypow(double x, in n) {...
}

5）递归的优缺点

优点：结构清晰，程序易读。

缺点：每次调用要生成工作记录，保存状态信息，入栈;返回时要出栈恢复状态信息。时间开销大。

6）递归 -> 非递归

方法1：尾递归、单向递归→循环结构

方法2：自用栈模拟系统的运行时栈

• 递归程序在执行时需要系统提供栈来实现
• 仿照递归算法执行过程中递归工作栈的状态变化可写出相应的非递归程序
• 改写后的非递归算法与原来的递归算法相比，结构不够清晰，可读性较差有的还需要经过一系列优化

四、队列

1）概念：

队列(queue)是一种先进先出（Frist In Frist Out ----FIFO）的线性表。在表一端插入(表尾)，在另一端(表头)删除。

2）特点：先进先出

3）示意图：

4）常见问题：

脱机打印输出:按申请的先后顺序依次输出。
多用户系统中，多个用户排成队，分时地循环使用CPU和主存。
按用户的优先级排成多个队，每个优先级一个队列。
实时控制系统中，信号按接收的先后顺序依次处理。
网络电文传输，按到达的时间先后顺序依次进行。

5）队列的表示：

• 队列(Queue)是仅在 表尾 进行插入操作，在 表头 进行删除操作的线性表。
• 表尾即an端，称为队尾；表头即a1端，称为队头。
• 它是一种先进先出( FIFO )的线性表。

例如：队列 Q = (a1, a2 a3 .. an-1. an)

插入元素称为入队删除元素称为出队

队列的存储结构为链队或顺序队(常用循环顺序队)

6）循环顺序队的表示与实现

1、真溢出与假溢出

真溢出是数组没有空位再入新的元素了。

假溢出是数组中不按原来顺序依次放入，以按其他顺序还有空位可以放入新的元素。

解决假上溢的方法：

2、解决假上溢方法——引入循环队列

base[0] 接在base[MAXQSIZE - 1] 之后，若rear + 1 == M，则令rear = 0

实现方法：利用模(mod，C语言中:%)运算。

因为如上图所示：

• 当在 0 位置时，（0 + 1）% 6 = 1
• 当在 1 位置时，（1 + 1）% 6 = 2
• …
• 当在 5 位置时，数组满时，（5 + 1）% 6 = 0 回到 0 位置

​ 所以：

插入元素：Q.base[Q.rear] = x;Q.rear = (Q.rear + 1) % MAXQSIZE // 达到最大值等于0,回到原点删除元素:x = Q.base[s.front];Q.front = (Q.front + 1) % MAXQSIZE

3、解决队空队满如何判定的方法

4、定义循环顺序表队列结构

#include <iostream>
#include <stdexcept>using namespace std;
#define MAXSIZE 100  // 队列的最大容量
#define OK 1    //成功标识
#define ERROR 0 //失败标识typedef int QElemType;  // 队列元素的类型，这里假定为int
typedef int Status;typedef struct {QElemType data[MAXSIZE];  // 存储队列元素的数组// QElemType *base;       // 动态分配存储空间int front;                // 头指针int rear;                 // 尾指针
} SqQueue;

5、循环顺序表队列的初始化

// 初始化队列
Status InitQueue(SqQueue& Q) {// Q.base = new QElemType[MAXQSIZE] // 分配数组空间// Q.base = (QElemType*) malloc (MAXQSIZE *sizeof(QElemType)); // 动态分配空间// if (!Q.base) exit(OVERFLOW);  // 存储分配失败Q.front = 0; // 头指针Q.rear = 0;  // 尾指针return OK;
}

6、循环顺序表队列的清空与销毁

// 销毁队列
Status DestroyQueue(SqQueue& Q) {// 顺序表实现的队列不需要显式释放内存Q.front = 0;Q.rear = 0;return OK;
}// 清空队列
Status ClearQueue(SqQueue& Q) {Q.front = 0;Q.rear = 0;return OK;
}

7、求循环顺序表队列长度和判断循环顺序表队列是否为空

// 获取队列的长度
int QueueLength(SqQueue Q) {return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}// 判断队列是否为空
bool QueueEmpty(SqQueue Q) {return Q.front == Q.rear;
}

8、循环顺序表队列的入队

// 入队操作
Status EnQueue(SqQueue& Q, QElemType e) {if ((Q.rear + 1) % MAXSIZE == Q.front) {  // 队列满return ERROR;}Q.data[Q.rear] = e;Q.rear = (Q.rear + 1) % MAXSIZE;  // 循环队列 队尾 + 1return OK;
}

9、循环顺序表队列的出队

// 出队操作
Status DeQueue(SqQueue& Q, QElemType& e) {if (Q.front == Q.rear) {  // 队列空return ERROR;}e = Q.data[Q.front];Q.front = (Q.front + 1) % MAXSIZE;  // 循环队列 队头 + 1return OK;
}

10、获取循环顺序表队列顶元素

// 获取队列头部元素
Status GetHead(SqQueue Q, QElemType& e) {if (Q.front == Q.rear) {  // 队列空return ERROR;}e = Q.data[Q.front];return OK;
}

11、运行测试

// 打印队列内元素
void PrintQueue(SqQueue Q) {if (Q.front == Q.rear) {cout << "队列为空" << endl;return;}cout << "队列为: ";int i = Q.front;while (i != Q.rear) {cout << Q.data[i] << " ";i = (i + 1) % MAXSIZE;}cout << endl;
}int main() {SqQueue queue;InitQueue(queue);int choice, value;bool running = true;while (running) {cout << "1. 入队\n2. 出队\n3. 获得队头元素\n4. 判断队列是否为空\n5. 清空队列\n6. 获得队列长度\n7. 打印队列\n8. 退出\n";cout << "请输入你的选择: ";cin >> choice;switch (choice) {case 1:cout << "请输入要入队的元素: ";cin >> value;if (EnQueue(queue, value) == OK) {cout << "入队成功" << endl;}else {cout << "队列已满" << endl;}PrintQueue(queue);break;case 2:if (DeQueue(queue, value) == OK) {cout << "出队的元素: " << value << endl;}else {cout << "队列为空" << endl;}PrintQueue(queue);break;case 3:if (GetHead(queue, value) == OK) {cout << "队头元素为: " << value << endl;}else {cout << "队列为空" << endl;}break;case 4:if (QueueEmpty(queue)) {cout << "队列为空" << endl;}else {cout << "队列不为空" << endl;}break;case 5:ClearQueue(queue);cout << "队列已清空" << endl;PrintQueue(queue);break;case 6:cout << "队列长度: " << QueueLength(queue) << endl;break;case 7:PrintQueue(queue);break;case 8:running = false;break;default:cout << "Invalid choice" << endl;break;}}DestroyQueue(queue);return 0;
}

12、总体代码

#include <iostream>
#include <stdexcept>using namespace std;
#define MAXSIZE 100  // 队列的最大容量
#define OK 1    //成功标识
#define ERROR 0 //失败标识typedef int QElemType;  // 队列元素的类型，这里假定为int
typedef int Status;typedef struct {QElemType data[MAXSIZE];  // 存储队列元素的数组// QElemType *base;       // 动态分配存储空间int front;                // 头指针int rear;                 // 尾指针
} SqQueue;// 初始化队列
Status InitQueue(SqQueue& Q) {// Q.base = new QElemType[MAXQSIZE] // 分配数组空间// Q.base = (QElemType*) malloc (MAXQSIZE *sizeof(QElemType)); // 动态分配空间// if (!Q.base) exit(OVERFLOW);  // 存储分配失败Q.front = 0; // 头指针Q.rear = 0;  // 尾指针return OK;
}// 销毁队列
Status DestroyQueue(SqQueue& Q) {// 顺序表实现的队列不需要显式释放内存Q.front = 0;Q.rear = 0;return OK;
}// 入队操作
Status EnQueue(SqQueue& Q, QElemType e) {if ((Q.rear + 1) % MAXSIZE == Q.front) {  // 队列满return ERROR;}Q.data[Q.rear] = e;Q.rear = (Q.rear + 1) % MAXSIZE;  // 循环队列 队尾 + 1return OK;
}// 出队操作
Status DeQueue(SqQueue& Q, QElemType& e) {if (Q.front == Q.rear) {  // 队列空return ERROR;}e = Q.data[Q.front];Q.front = (Q.front + 1) % MAXSIZE;  // 循环队列 队头 + 1return OK;
}// 获取队列头部元素
Status GetHead(SqQueue Q, QElemType& e) {if (Q.front == Q.rear) {  // 队列空return ERROR;}e = Q.data[Q.front];return OK;
}// 判断队列是否为空
bool QueueEmpty(SqQueue Q) {return Q.front == Q.rear;
}// 清空队列
Status ClearQueue(SqQueue& Q) {Q.front = 0;Q.rear = 0;return OK;
}// 获取队列的长度
int QueueLength(SqQueue Q) {return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}// 打印队列内元素
void PrintQueue(SqQueue Q) {if (Q.front == Q.rear) {cout << "队列为空" << endl;return;}cout << "队列为: ";int i = Q.front;while (i != Q.rear) {cout << Q.data[i] << " ";i = (i + 1) % MAXSIZE;}cout << endl;
}int main() {SqQueue queue;InitQueue(queue);int choice, value;bool running = true;while (running) {cout << "1. 入队\n2. 出队\n3. 获得队头元素\n4. 判断队列是否为空\n5. 清空队列\n6. 获得队列长度\n7. 打印队列\n8. 退出\n";cout << "请输入你的选择: ";cin >> choice;switch (choice) {case 1:cout << "请输入要入队的元素: ";cin >> value;if (EnQueue(queue, value) == OK) {cout << "入队成功" << endl;}else {cout << "队列已满" << endl;}PrintQueue(queue);break;case 2:if (DeQueue(queue, value) == OK) {cout << "出队的元素: " << value << endl;}else {cout << "队列为空" << endl;}PrintQueue(queue);break;case 3:if (GetHead(queue, value) == OK) {cout << "队头元素为: " << value << endl;}else {cout << "队列为空" << endl;}break;case 4:if (QueueEmpty(queue)) {cout << "队列为空" << endl;}else {cout << "队列不为空" << endl;}break;case 5:ClearQueue(queue);cout << "队列已清空" << endl;PrintQueue(queue);break;case 6:cout << "队列长度: " << QueueLength(queue) << endl;break;case 7:PrintQueue(queue);break;case 8:running = false;break;default:cout << "Invalid choice" << endl;break;}}DestroyQueue(queue);return 0;
}

13、运行结果

7）链队的表示与实现

1、定义链队结构

#include <iostream>
#include <stdexcept>using namespace std;#define OK 1    //成功标识
#define ERROR 0 //失败标识typedef int QElemType;  // 队列元素的类型，这里假定为int
typedef int Status;typedef struct QueueNode {QElemType data;struct QueueNode* next;
} QueueNode, * QueuePtr;typedef struct {QueuePtr front;  // 头指针QueuePtr rear;   // 尾指针
} LinkQueue;

2、链队的初始化

// 初始化队列
Status InitQueue(LinkQueue& Q) {// Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode)) // 动态分配内存空间Q.front = Q.rear = new QueueNode;  // 创建头结点if (Q.front == NULL) return ERROR; // 内存分配失败Q.front->next = NULL;return OK;
}

3、链队的清空与销毁

// 销毁队列
Status DestroyQueue(LinkQueue& Q) {while (Q.front != NULL) {QueuePtr p = Q.front;Q.front = Q.front->next;delete p;}return OK;
}// 清空队列
Status ClearQueue(LinkQueue& Q) {DestroyQueue(Q);return InitQueue(Q);
}

4、求链队长度和判断链队是否为空

// 获取队列的长度
int QueueLength(LinkQueue Q) {int length = 0;QueuePtr p = Q.front->next;while (p != NULL) {length++;p = p->next;}return length;
}// 判断队列是否为空
bool QueueEmpty(LinkQueue Q) {return Q.front == Q.rear;
}

5、链队的入队

// 入队操作
Status EnQueue(LinkQueue& Q, QElemType e) {QueuePtr s = new QueueNode;  // 创建新节点if (s == NULL) return ERROR; // 内存分配失败s->data = e;s->next = NULL;Q.rear->next = s;Q.rear = s;return OK;
}

6、链队的出队

// 出队操作
Status DeQueue(LinkQueue& Q, QElemType& e) {if (Q.front == Q.rear) return ERROR;  // 队列空QueuePtr p = Q.front->next;e = p->data;Q.front->next = p->next;if (p->next == NULL) Q.rear = Q.front;  // 如果队列变为空，更新尾指针delete p;return OK;
}

7、获取队顶元素

// 获取队列头部元素
Status GetHead(LinkQueue Q, QElemType& e) {if (Q.front == Q.rear) return ERROR;  // 队列空e = Q.front->next->data;return OK;
}

8、运行测试

// 打印队列内元素
void PrintQueue(LinkQueue Q) {if (Q.front == Q.rear) {cout << "队列为空" << endl;return;}cout << "队列为: ";QueuePtr p = Q.front->next;while (p != NULL) {cout << p->data << " ";p = p->next;}cout << endl;
}int main() {LinkQueue queue;InitQueue(queue);int choice, value;bool running = true;while (running) {cout << "1.入队\n2.出队\n3.获得队头元素\n4.判断队列是否为空\n5.清空队列\n6.获得队列长度\n7.打印队列\n8.退出\n";cout << "请输入你的选择: ";cin >> choice;switch (choice) {case 1:cout << "请输入要入队的元素:  ";cin >> value;if (EnQueue(queue, value) == OK) {cout << "入队成功"  << endl;}else {cout << "入队失败" << endl;}PrintQueue(queue);break;case 2:if (DeQueue(queue, value) == OK) {cout << "出队的元素:  " << value << endl;}else {cout << "队列为空" << endl;}PrintQueue(queue);break;case 3:if (GetHead(queue, value) == OK) {cout << "队头元素为: " << value << endl;}else {cout << "队列为空" << endl;}break;case 4:if (QueueEmpty(queue)) {cout << "队列为空" << endl;}else {cout << "队列不为空" << endl;}break;case 5:ClearQueue(queue);cout << "队列已清空" << endl;PrintQueue(queue);break;case 6:cout << "队列长度为: " << QueueLength(queue) << endl;break;case 7:PrintQueue(queue);break;case 8:running = false;break;default:cout << "Invalid choice" << endl;break;}}DestroyQueue(queue);return 0;
}

9、总体代码

#include <iostream>
#include <stdexcept>using namespace std;#define OK 1    //成功标识
#define ERROR 0 //失败标识typedef int QElemType;  // 队列元素的类型，这里假定为int
typedef int Status;typedef struct QueueNode {QElemType data;struct QueueNode* next;
} QueueNode, * QueuePtr;typedef struct {QueuePtr front;  // 头指针QueuePtr rear;   // 尾指针
} LinkQueue;// 初始化队列
Status InitQueue(LinkQueue& Q) {// Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode)) // 动态分配内存空间Q.front = Q.rear = new QueueNode;  // 创建头结点if (Q.front == NULL) return ERROR; // 内存分配失败Q.front->next = NULL;return OK;
}// 销毁队列
Status DestroyQueue(LinkQueue& Q) {while (Q.front != NULL) {QueuePtr p = Q.front;Q.front = Q.front->next;delete p;}return OK;
}// 入队操作
Status EnQueue(LinkQueue& Q, QElemType e) {QueuePtr s = new QueueNode;  // 创建新节点if (s == NULL) return ERROR; // 内存分配失败s->data = e;s->next = NULL;Q.rear->next = s;Q.rear = s;return OK;
}// 出队操作
Status DeQueue(LinkQueue& Q, QElemType& e) {if (Q.front == Q.rear) return ERROR;  // 队列空QueuePtr p = Q.front->next;e = p->data;Q.front->next = p->next;if (p->next == NULL) Q.rear = Q.front;  // 如果队列变为空，更新尾指针delete p;return OK;
}// 获取队列头部元素
Status GetHead(LinkQueue Q, QElemType& e) {if (Q.front == Q.rear) return ERROR;  // 队列空e = Q.front->next->data;return OK;
}// 判断队列是否为空
bool QueueEmpty(LinkQueue Q) {return Q.front == Q.rear;
}// 清空队列
Status ClearQueue(LinkQueue& Q) {DestroyQueue(Q);return InitQueue(Q);
}// 获取队列的长度
int QueueLength(LinkQueue Q) {int length = 0;QueuePtr p = Q.front->next;while (p != NULL) {length++;p = p->next;}return length;
}// 打印队列内元素
void PrintQueue(LinkQueue Q) {if (Q.front == Q.rear) {cout << "队列为空" << endl;return;}cout << "队列为: ";QueuePtr p = Q.front->next;while (p != NULL) {cout << p->data << " ";p = p->next;}cout << endl;
}int main() {LinkQueue queue;InitQueue(queue);int choice, value;bool running = true;while (running) {cout << "1.入队\n2.出队\n3.获得队头元素\n4.判断队列是否为空\n5.清空队列\n6.获得队列长度\n7.打印队列\n8.退出\n";cout << "请输入你的选择: ";cin >> choice;switch (choice) {case 1:cout << "请输入要入队的元素:  ";cin >> value;if (EnQueue(queue, value) == OK) {cout << "入队成功"  << endl;}else {cout << "入队失败" << endl;}PrintQueue(queue);break;case 2:if (DeQueue(queue, value) == OK) {cout << "出队的元素:  " << value << endl;}else {cout << "队列为空" << endl;}PrintQueue(queue);break;case 3:if (GetHead(queue, value) == OK) {cout << "队头元素为: " << value << endl;}else {cout << "队列为空" << endl;}break;case 4:if (QueueEmpty(queue)) {cout << "队列为空" << endl;}else {cout << "队列不为空" << endl;}break;case 5:ClearQueue(queue);cout << "队列已清空" << endl;PrintQueue(queue);break;case 6:cout << "队列长度为: " << QueueLength(queue) << endl;break;case 7:PrintQueue(queue);break;case 8:running = false;break;default:cout << "Invalid choice" << endl;break;}}DestroyQueue(queue);return 0;
}

10、运行结果