顺序栈与链队列

实验内容

(1)建立顺序栈，并将元素(8，9，5，4)入栈，实现顺序栈的建立及入栈的基本操作；

(2)实现元素(8，9)的出栈，实现顺序栈的出栈操作；

(3)建立链队列，并将元素(4,5,7,6,8)入队,实现链队列的建立和入队的基本操作;

(4)实现元素(4，5)出队，实现链队列的出队操作:

(5)菜单操作。

1.顺序栈（不用指针版

#define ERROR 0
#define OK 1
#define OVERFLOW -2#define STACK_INIT_SIZE 100  //存储空间初始分配量 
#define STACKINCREMENT 10  //存储空间分配增量#include <stdio.h>
#include <stdlib.h> //用malloc时要声明，引入stdlib.h以使用malloc和realloc  typedef int SElemType; // 定义栈元素类型为整型
typedef int Status;    // 定义状态类型为整型typedef struct{SElemType *base;  //在栈构造之前和销毁之后，base的值为NULL SElemType *top;  //栈顶指针 int stacksize;  //当前已分配的存储空间，以元素为单位 
}SqStack;//构造一个空栈S
Status InitStack(SqStack &S){ S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));if(!S.base)exit(OVERFLOW);  //存储分配失败 S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;
}//InitStack//取栈顶元素 
Status GetTop(SqStack S,SElemType &e){//若栈不空，则用e返回S的栈顶元素，并返回OK，否则返回ERROR if(S.top==S.base)return ERROR;e=*(S.top-1);  //返回非空栈中栈顶元素 return OK;
}//GetTop//进栈操作
Status Push(SqStack &S,SElemType e){//插入元素e为新的栈顶元素if(S.top-S.base>=S.stacksize){  //栈满，追加存储空间S.base=(SElemType *)realloc(S.base,(S.stacksize + STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);  // 存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT; } *S.top++=e;  //插入新元素，栈顶指针后移return OK; 
} //Push//出栈操作
Status Pop(SqStack &S,SElemType &e){//若栈不空，则删除S的栈顶元素，用e返回其值，并返回ok，否则返回errorif(S.top==S.base)return ERROR;e=*--S.top;  //返回非空栈中的栈顶元素，栈顶指针后移//相当于e=*(S.top-1) return OK; 
} //Pop// 销毁栈
void DestroyStack(SqStack *S) {if (S->base) {free(S->base); // 释放栈空间S->base = NULL; // 设置为NULL}S->top = NULL;S->stacksize = 0;
}// 测试主函数
int main() {SqStack S;SElemType e;  //非常注意！这里是一个变量，不是指针if (InitStack(S) != OK) {printf("初始化栈失败！\n");return -1;}// 进栈操作Push(S, 8);Push(S, 9);Push(S, 5);Push(S, 4);//出栈操作 if (Pop(S, e) == OK) {//当前面 Pop 引用参数时以&打头，除可提供输入值外，还将返回操作结果 //所以这里 S 和 e 不用加 &  printf("出栈元素: %d\n", e); //应该是4 }if (Pop(S, e) == OK) {printf("出栈元素: %d\n", e); // 应该是5}// 输出栈顶元素if (GetTop(S, e) == OK) {printf("栈顶元素: %d\n", e); // 应该是9}DestroyStack(&S); // 销毁栈return 0;
}

顺序栈（加上菜单版

#define ERROR 0
#define OK 1
#define OVERFLOW -2#define STACK_INIT_SIZE 100  //存储空间初始分配量 
#define STACKINCREMENT 10  //存储空间分配增量#include <stdio.h>
#include <stdlib.h> //用malloc时要声明，引入stdlib.h以使用malloc和realloc  typedef int SElemType; // 定义栈元素类型为整型
typedef int Status;    // 定义状态类型为整型typedef struct{SElemType *base;  //在栈构造之前和销毁之后，base的值为NULL SElemType *top;  //栈顶指针 int stacksize;  //当前已分配的存储空间，以元素为单位 
}SqStack;//构造一个空栈S
Status InitStack(SqStack &S){ S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));if(!S.base)exit(OVERFLOW);  //存储分配失败 S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;
}//InitStack//取栈顶元素 
Status GetTop(SqStack S,SElemType &e){//若栈不空，则用e返回S的栈顶元素，并返回OK，否则返回ERROR if(S.top==S.base)return ERROR;e=*(S.top-1);  //返回非空栈中栈顶元素 return OK;
}//GetTop//进栈操作
Status Push(SqStack &S,SElemType e){//插入元素e为新的栈顶元素if(S.top-S.base>=S.stacksize){  //栈满，追加存储空间S.base=(SElemType *)realloc(S.base,(S.stacksize + STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);  // 存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT; } *S.top++=e;  //插入新元素，栈顶指针后移return OK; 
} //Push//出栈操作
Status Pop(SqStack &S,SElemType &e){//若栈不空，则删除S的栈顶元素，用e返回其值，并返回ok，否则返回errorif(S.top==S.base)return ERROR;e=*--S.top;  //返回非空栈中的栈顶元素，栈顶指针后移//相当于e=*(S.top-1) return OK; 
} //Pop// 销毁栈
void DestroyStack(SqStack *S) {if (S->base) {free(S->base); // 释放栈空间S->base = NULL; // 设置为NULL}S->top = NULL;S->stacksize = 0;
}// 显示菜单
void ShowMenu() {printf("\n----- 顺序栈操作菜单 -----\n");printf("1. 入栈\n");printf("2. 出栈\n");printf("3. 查看栈顶元素\n");printf("4. 销毁栈\n");printf("0. 退出\n");printf("--------------------------\n");
}// 测试主函数
int main() {SqStack S;SElemType e;  //非常注意！这里是一个变量，不是指针int choice;if (InitStack(S) != OK) {printf("初始化栈失败！\n");return -1;}while (1) {ShowMenu();printf("请输入您的选择: ");scanf("%d", &choice);switch (choice) {case 1: // 入栈printf("请输入要入栈的元素: ");scanf("%d", &e);if (Push(S, e) == OK) {printf("%d 入栈成功。\n", e);} else {printf("入栈失败，存储溢出！\n");}break;case 2: // 出栈if (Pop(S, e) == OK) {//当前面 Pop 引用参数时以&打头，除可提供输入值外，还将返回操作结果 //所以这里 S 和 e 不用加 & printf("出栈元素: %d\n", e);} else {printf("出栈失败，栈为空！\n");}break;case 3: // 查看栈顶元素if (GetTop(S, e) == OK) {printf("栈顶元素: %d\n", e);} else {printf("栈为空，无法查看栈顶元素！\n");}break;case 4: // 销毁栈DestroyStack(&S);printf("栈已销毁。\n");return 0; // 退出程序case 0: // 退出DestroyStack(&S);printf("退出程序。\n");return 0;default:printf("无效的选择，请重新输入。\n");break;}}return 0;
}

2.链队列

#define ERROR 0
#define OK 1
#define OVERFLOW -2#include <stdio.h>
#include <stdlib.h> //用malloc时要声明，引入stdlib.h以使用malloc和realloc  typedef int QElemType; // 定义队列元素类型为整型
typedef int Status;    // 定义状态类型为整型typedef struct QNode{QElemType data;struct QNode *next;
}Qnode, *QueuePtr;typedef struct{QueuePtr front;  //队头指针 QueuePtr rear;  //队尾指针 
}LinkQueue;Status InitQueue(LinkQueue &Q){//构造一个空队列QQ.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);  //存储分配失败Q.front->next = NULL;return OK; 
}Status DestroyQueue(LinkQueue &Q){//销毁队列QQueuePtr p; //在 EnQueue 和 DeQueue 函数中，变量 p 没有声明//应在函数开始时声明 QueuePtr p;while(Q.front){Q.rear = Q.front->next;free(Q.front);Q.front = Q.rear;}return OK;
}Status EnQueue(LinkQueue &Q,QElemType e){//插入元素e为Q的新的队尾元素QueuePtr p;p = (QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);  //存储分配失败p->data = e;p->next = NULL;Q.rear->next = p;Q.rear = p;return OK; 
}Status DeQueue(LinkQueue &Q,QElemType &e){//若队列不为空，则删除Q的队头元素，用e返回其值，并返回OK；//否则返回ERROR；QueuePtr p;if (Q.front == Q.rear)return ERROR;p = Q.front->next;e = p->data;Q.front->next = p->next;if(Q.rear == p)Q.rear=Q.front;free(p);return OK;
}// 显示菜单
void ShowMenu() {printf("\n----- 链式队列操作菜单 -----\n");printf("1. 入队\n");printf("2. 出队\n");printf("3. 销毁队列\n");printf("0. 退出\n");printf("--------------------------\n");
}// 主函数
int main() {LinkQueue Q;QElemType e;Status status;// 初始化队列if (InitQueue(Q) != OK) {  //不用& printf("初始化队列失败！\n");return -1;}int choice;while (1) {ShowMenu();scanf("%d", &choice);switch (choice) {case 1: // 入队printf("请输入入队元素: ");scanf("%d", &e);status = EnQueue(Q, e); //不用& if (status == OK) {printf("元素 %d 入队成功。\n", e);} else {printf("入队失败，内存溢出！\n");}break;case 2: // 出队status = DeQueue(Q, e);  //不用& if (status == OK) {printf("元素 %d 出队成功。\n", e);} else {printf("出队失败，队列为空！\n");}break;case 3: // 销毁队列status = DestroyQueue(Q);  //不用& if (status == OK) {printf("队列已销毁。\n");}break;case 0: // 退出DestroyQueue(Q); // 确保退出前销毁队列return 0;default:printf("无效的选项，请重试。\n");}}return 0;
}

3.合并版

为了实现结束顺序栈或链队列的基本操作后能返回主菜单的功能，需要在相应的子菜单操作循环中增加对返回上一级（即主菜单）的处理。这可以通过在接收到特定指令（例如输入0）时跳出当前子菜单的循环来实现。

增加了一个名为inSubMenu的变量来跟踪当前是否处于子菜单中。当用户选择0来退出子菜单时，inSubMenu被设置为0，从而跳出子菜单的循环并返回到主菜单。如果用户选择退出程序（即主菜单中的0），则程序将销毁栈和队列并退出。

下面是修改后的代码，其中增加了返回主菜单的功能：

#define ERROR 0
#define OK 1
#define OVERFLOW -2#define STACK_INIT_SIZE 100  // 存储空间初始分配量 
#define STACKINCREMENT 10     // 存储空间分配增量#include <stdio.h>
#include <stdlib.h> // 用malloc时要声明，引入stdlib.h以使用malloc和realloc  typedef int SElemType; // 定义栈元素类型为整型
typedef int QElemType; // 定义队列元素类型为整型
typedef int Status;    // 定义状态类型为整型// 顺序栈定义
typedef struct {SElemType *base;  // 在栈构造之前和销毁之后，base的值为NULL SElemType *top;   // 栈顶指针 int stacksize;    // 当前已分配的存储空间，以元素为单位 
} SqStack;// 链队列定义
typedef struct QNode {QElemType data;struct QNode *next;
} QNode, *QueuePtr;typedef struct {QueuePtr front;  // 队头指针 QueuePtr rear;   // 队尾指针 
} LinkQueue;// 栈操作函数
//构造一个空栈S
Status InitStack(SqStack &S) { S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));if (!S.base) exit(OVERFLOW);  // 存储分配失败 S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;
}//InitStack//取栈顶元素 
Status GetTop(SqStack S,SElemType &e){//若栈不空，则用e返回S的栈顶元素，并返回OK，否则返回ERROR if(S.top==S.base)return ERROR;e=*(S.top-1);  //返回非空栈中栈顶元素 return OK;
}//GetTop//进栈操作
Status Push(SqStack &S,SElemType e){//插入元素e为新的栈顶元素if(S.top - S.base >= S.stacksize){  //栈满，追加存储空间S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) *sizeof(SElemType));if(!S.base) exit(OVERFLOW);  // 存储分配失败S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT; } *S.top++ = e;  //插入新元素，栈顶指针后移return OK; 
} //Push//出栈操作
Status Pop(SqStack &S,SElemType &e){//若栈不空，则删除S的栈顶元素，用e返回其值，并返回ok，否则返回errorif(S.top == S.base) return ERROR;e= *--S.top;  //返回非空栈中的栈顶元素，栈顶指针后移//相当于e=*(S.top-1) return OK; 
} //Pop// 销毁栈
void DestroyStack(SqStack *S) {if (S->base) {free(S->base); // 释放栈空间S->base = NULL; // 设置为NULL}S->top = NULL;S->stacksize = 0;
}// 队列操作函数
Status InitQueue(LinkQueue &Q){//构造一个空队列QQ.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);  //存储分配失败Q.front->next = NULL;return OK; 
}Status DestroyQueue(LinkQueue &Q){//销毁队列QQueuePtr p; //在 EnQueue 和 DeQueue 函数中，变量 p 没有声明//应在函数开始时声明 QueuePtr p;while(Q.front){Q.rear = Q.front->next;free(Q.front);Q.front = Q.rear;}return OK;
}Status EnQueue(LinkQueue &Q,QElemType e){//插入元素e为Q的新的队尾元素QueuePtr p;p = (QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);  //存储分配失败p->data = e;p->next = NULL;Q.rear->next = p;Q.rear = p;return OK; 
}Status DeQueue(LinkQueue &Q,QElemType &e){//若队列不为空，则删除Q的队头元素，用e返回其值，并返回OK；//否则返回ERROR；QueuePtr p;if (Q.front == Q.rear)return ERROR;p = Q.front->next;e = p->data;Q.front->next = p->next;if(Q.rear == p)Q.rear=Q.front;free(p);return OK;
}// 显示菜单
void ShowStackMenu() {printf("\n----- 顺序栈操作菜单 -----\n");printf("1. 入栈\n");printf("2. 出栈\n");printf("3. 查看栈顶元素\n");printf("4. 销毁栈\n");printf("0. 返回上一级\n");printf("--------------------------\n");
}void ShowQueueMenu() {printf("\n----- 链式队列操作菜单 -----\n");printf("1. 入队\n");printf("2. 出队\n");printf("3. 销毁队列\n");printf("0. 返回上一级\n");printf("--------------------------\n");
}// 主函数
int main() {SqStack S;LinkQueue Q;SElemType e;QElemType q_elem;int choice;int inSubMenu = 0; // 用于标记是否在子菜单中 // 初始化栈和队列InitStack(S);InitQueue(Q);// 入栈元素(8, 9, 5, 4)Push(S, 8);Push(S, 9);Push(S, 5);Push(S, 4);printf("顺序栈初始化并入栈了元素(8, 9, 5, 4)\n");// 入队元素(4, 5, 7, 6, 8)EnQueue(Q, 4);EnQueue(Q, 5);EnQueue(Q, 7);EnQueue(Q, 6);EnQueue(Q, 8);printf("链队列初始化并入队了元素(4, 5, 7, 6, 8)\n");while (1) {printf("\n----- 主菜单 -----\n");printf("1. 顺序栈操作\n");printf("2. 链式队列操作\n");printf("0. 退出\n");printf("------------------\n");printf("请输入您的选择: ");scanf("%d", &choice);switch (choice) {case 1: // 顺序栈操作inSubMenu = 1; // 进入子菜单while (inSubMenu) {ShowStackMenu();printf("请输入您的选择: ");scanf("%d", &choice);switch (choice) {case 1: // 入栈printf("请输入要入栈的元素: ");scanf("%d", &e);Push(S, e);printf("%d 入栈成功。\n", e);break;case 2: // 出栈if (Pop(S, e) == OK) {//当前面 Pop 引用参数时以&打头，提供输入值,返回操作结果 //所以这里 S 和 e 不用加 & printf("出栈元素: %d\n", e);} else {printf("出栈失败，栈为空！\n");}break;case 3: // 查看栈顶元素if (GetTop(S, e) == OK) {printf("栈顶元素: %d\n", e);} else {printf("栈为空，无法查看栈顶元素！\n");}break;case 4: // 销毁栈DestroyStack(&S);printf("栈已销毁。\n");inSubMenu = 0; // 退出子菜单，返回主菜单break; case 0: // 返回上一级(主菜单）inSubMenu = 0;  //退出子菜单，返回主菜单 break;default:printf("无效的选择，请重新输入。\n");break;}}break;case 2: // 链式队列操作inSubMenu = 1; //进入子菜单 while (inSubMenu) {ShowQueueMenu();printf("请输入您的选择: ");scanf("%d", &choice);switch (choice) {case 1: // 入队printf("请输入入队元素: ");scanf("%d", &q_elem);EnQueue(Q, q_elem); //不用&printf("元素 %d 入队成功。\n", q_elem);break;case 2: // 出队if (DeQueue(Q, q_elem) == OK) {printf("元素 %d 出队成功。\n", q_elem);} else {printf("出队失败，队列为空！\n");}break;case 3: // 销毁队列DestroyQueue(Q);printf("队列已销毁。\n");inSubMenu = 0; // 退出子菜单，返回主菜单 case 0: // 返回上一级（主菜单）inSubMenu = 0; //退出子菜单，返回主菜单 break;default:printf("无效的选项，请重试。\n");}}break;case 0: // 退出DestroyStack(&S);DestroyQueue(Q);printf("退出程序。\n");return 0;default:printf("无效的选择，请重新输入。\n");break;}}return 0;
}