魔王语言——栈和队列的应用

栈和队列常见数据结构的应用与实现栈和队列是常见的数据结构，它们在计算机科学中有着广泛的应用与实现。

本文将介绍栈和队列的基本概念、使用场景以及具体实现方式。

一、栈的概念和应用栈是一种先进后出（Last-In-First-Out, LIFO）的数据结构，类似于我们生活中的“堆叠”。

在栈中，元素的插入和删除操作都在同一端进行，这一端被称为栈顶。

栈的应用非常广泛，其中一个典型的应用是函数的调用与返回。

在函数调用时，局部变量和参数等数据被依次压入栈中，而函数返回时则会依次从栈中弹出这些数据。

这一过程使得函数间的数据传递和操作非常方便。

另外，栈还常用于表达式求值、括号匹配、浏览器的前进后退功能等场景。

二、栈的实现栈的实现有多种方式，其中一种比较常见的是使用数组实现栈。

下面是一个简单的示例代码：```pythonclass Stack:def __init__(self):self.items = []def is_empty(self):return len(self.items) == 0def push(self, item):self.items.append(item)def pop(self):if not self.is_empty():return self.items.pop()else:raise Exception("Stack is empty") def peek(self):if not self.is_empty():return self.items[-1]else:raise Exception("Stack is empty") def size(self):return len(self.items)```上述代码中，我们使用Python中的列表来存储栈的元素，其中is_empty、push、pop、peek和size等方法分别实现了判断栈是否为空、入栈、出栈、查看栈顶元素和获取栈的大小等功能。

2/59
简单表达式采用字符数组exp表示，其中只含有“+”、 “-”、“*”、“/”、正整数和圆括号。
为了方便，假设该表达式都是合法的算术表达式，例 如，exp=“1+2*(4+12)”；
在设计相关算法中用到栈，这里采用顺序栈存储结构。
3/59
运算符位于两个操作数中间的表达式称为中缀表达 式。例如，1+2*3就是一个中缀表达式。
开始时，任何运算符都进栈 (：一个子表达式开始，进栈 栈顶为(：任何运算符进栈
)：退栈到（
只有大于栈顶的优先级，才进栈；否则退栈
10/59
while (从exp读取字符ch，ch!='\0') { ch为数字：将后续的所有数字均依次存放到postexp中，
并以字符'#'标志数值串结束; ch为左括号'('：将此括号进栈到Optr中; ch为右括号')'：将Optr中出栈时遇到的第一个左括号'('以前的运算符依次出
栈并存放到postexp中，然后将左括号'('出栈; ch为其他运算符：
if （栈空或者栈顶运算符为'('） 直接将ch进栈; else if (ch的优先级高于栈顶运算符的优先级)
直接将ch进栈; else
依次出栈并存入到postexp中，直到栈顶运算符优先级小于ch的优先级， 然后将ch进栈; } 若exp扫描完毕，则将Optr中所有运算符依次出栈并存放到postexp中。
中缀表达式的运算规则：“先乘除，后加减，从左到 右计算，先括号内，后括号外”。
因此，中缀表达式不仅要依赖运算符优先级，而且还 要处理括号。
4/59

栈与队列的应用栈(Stack)和队列(Queue)是计算机科学中常见的数据结构，它们分别具有先进后出（Last-In-First-Out, LIFO）和先进先出（First-In-First-Out, FIFO）的特性。

这两种数据结构在计算机领域有着广泛的应用，本文将介绍一些栈与队列的常见应用场景。

一、栈的应用1. 括号匹配栈常被用于判断表达式中的括号是否匹配。

通过遍历表达式中的每个字符，将左括号入栈，当遇到右括号时，检查栈顶元素与右括号是否匹配。

若匹配，则出栈；若不匹配，则说明括号不匹配。

2. 浏览器的前进与后退功能在浏览器中，我们可以通过点击前进和后退按钮来在不同的网页之间切换。

这种功能可以使用两个栈来实现：一个栈用于存储用户浏览的历史页面，另一个栈用于存储用户后退的页面。

当用户点击前进按钮时，从后退栈中弹出页面并推入历史页面栈；当用户点击后退按钮时，从历史页面栈中取出页面并推入后退页面栈。

3. 函数调用与递归在程序中，函数的调用是通过栈来实现的。

当一个函数被调用时，系统会将该函数的返回地址和参数等信息压入栈中；当函数执行完毕后，从栈中弹出返回地址，继续执行调用函数的下一条指令。

4. 表达式求值中缀表达式求值通常需要借助栈来实现。

通过将表达式转换成后缀表达式，并使用栈存储运算符和操作数，可以按照规定的优先级进行计算，得到最终的结果。

二、队列的应用1. 打印任务队列在计算机系统中，多个用户同时提交打印任务时，可以使用队列来管理这些任务。

每当有新的任务到达时，将其加入队列尾部，打印机则从队列头部取出任务进行打印。

这样可以保证任务的顺序性，并避免多个任务之间的冲突。

2. 消息队列在分布式系统中，消息队列通常用于解耦不同模块之间的通信。

一个模块可以将消息发送到队列中，而其他模块可以异步地从队列中获取消息并进行相应的处理。

这种方式提高了系统的可伸缩性和稳定性。

3. 广度优先搜索在图论中，广度优先搜索（Breadth-First Search, BFS）可以借助队列来实现。

数据结构与算法实验报告姓名院系学号任课教师指导教师实验地点软件学院实验时间2011年10月29 日实验名称数据结构实验一栈和队列同组人无预习报告(对实验主要内容的认识) 得分实验内容（问题，思路，程序，结果）得分1.题目：魔王语言2.问题描述：有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没有人能听得懂,但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的；α→β1β2…βm(θδ1δ2…δn)→δnθδn-1θ…δ2θδ1在这两种形式中，从左到右均表示解释。

试写一个魔王语言的解释系统，把他的话解释成人能听得懂得话。

3.算法思想描述（1）算法的思想①我将设置三个堆栈和两个队列处理这个问题，首先将魔王语言自右向左压入堆栈*2(一个用来测试S_3另一个用来操作S_1)，然后判断此句话中是否有括号，若无则直接将操作堆栈弹出到队列中然后输出；②若有括号则先弹出操作堆栈S_1到队列Q_1中,遇到"("时跳过这个括号然后将括号后面的第一个字母标记（记作A ），将除第一个字母外的其他字母弹出到队列Q_2中，直到遇到")"为止，将“）”弹出；③将Q_2的元素每后面一个加原来的第一个元素A 压入堆栈S_2;④将堆栈S_2的元素弹出到Q_1中，然后将S_1中剩余的元素弹出到Q_!; ⑤按照对应的字母翻译即可。

（2）算法流程图开始 是否有括号 直接将堆栈中的弹出入队列翻译输出 将魔王语言自右向左压入堆栈S_1 NO YES 将堆栈S_1中的元素弹出到Q_1 弹出元素为"(" YES NO 弹出（后第一个元素记为A 将剩余元素弹入队列Q_2中 NO弹出元素为）YES将Q_2元素每个加A压入栈S_2将S_2中的元素弹出到Q_1中将S_1中剩余元素弹出到Q_1中翻译后输出结果结束4.数据结构描述（描述解决问题用到的数据结构）（1）所用数据结构的描述S_1堆栈负责自右向左存放魔王语言S_2堆栈存放处理过的括号里的语言S_3堆栈负责判断是否有括号Q_1队列存放处理后的语言Q_2队列负责存放括号中的语言（2）函数功能说明及函数的实现源代码①堆栈实现#ifndef STACK_H_INCLUDED#define STACK_H_INCLUDED#include<stdio.h>#include<math.h>#include<stdlib.h>#include<string.h>#define MAXSIZE 100#define STACK_INIT_MAX 100#define STACKINCREMENT 10#define ERROR 0#define OK 1#define FALSE 0#define TRUE 1typedef int Status;typedef struct{ //顺序栈类型定义char *top;char *base;int stacksize;}SqStack;Status InitStack(SqStack &s){ //构造一个空栈ss.base=(char *)malloc(STACK_INIT_MAX*sizeof(char)); if(!s.base) exit(OVERFLOW); //存储分配失败s.top = s.base;s.stacksize = STACK_INIT_MAX;return OK;}Status Pop(SqStack &s,char &e){ //删除s的栈顶元素，并以e返回其值if(s.top == s.base) return FALSE;s.top--;e = *(s.top);return TRUE;}Status Push(SqStack &s,char e){ //在栈s的栈顶插入新的栈顶元素e if((s.top-s.base) >= s.stacksize){s.base=(char*)realloc(s.base,(s.stacksize+STACKINCREMENT) * sizeof(char));if(!s.base) exit(OVERFLOW); //存储分配失败s.top = s.base + s.stacksize;s.stacksize += STACKINCREMENT;}*s.top = e;s.top++;return OK;}Status DestroyStack(SqStack &s){ //销毁栈sfree(s.base);s.stacksize = 0;return OK;}void InStack(char* ch,SqStack &s){//把字符数组从右至左压入栈中int i,L=0;while(ch[L]!='\0'){L++;}for(i=L-1;i>=0;i--){Push(s,ch[i]);}}Status StackEmpty(SqStack s){//栈是否为空if(s.top==s.base){return 1;}else{return 0;}}#endif // STACK_H_INCLUDED②队列实现#ifndef QUEUE_H_INCLUDED #define QUEUE_H_INCLUDED #include<stdio.h>#include<math.h>#include<stdlib.h>#include<string.h>#define MAXSIZE 100#define ERROR 0#define OK 1#define FALSE 0#define TRUE 1typedef struct{ //循环队列类型定义char *base;int front;int rear;}SqQueue;Status InitQueue(SqQueue &q){ //构造一个空队列qq.base = (char *)malloc(MAXSIZE*sizeof(char));if(!q.base) exit(OVERFLOW); //存储分配失败q.front = q.rear = 0;return OK;}Status EnQueue(SqQueue &q,char e){ //插入元素e为q的新的队尾元素if((q.rear+1) % MAXSIZE == q.front) return ERROR;q.base[q.rear] = e;q.rear = (q.rear + 1) % MAXSIZE;return OK;}Status DeQueue(SqQueue &q,char &e){ //若队列不空，则删除q的对头元素，用e返回其值，//并返回OK；否则返回ERRORif(q.front == q.rear) return ERROR;e = q.base[q.front];q.front = (q.front + 1) % MAXSIZE;return OK;}Status DestroyQueue(SqQueue &q){ //销毁队列q，q不再存在free(q.base);return OK;}#endif // QUEUE_H_INCLUDED③main函数实现#include <iostream>#include"Stack.h"#include"Queue.h"int main(){int length,i,mark; //length表示魔王语言的长度，mark为"("数mark=0;char e,str,j; //e为插入值或删除值，str为重复打印的字符，j为检测符char MoWang[100];//用来储存魔王的语言SqStack S_1;SqStack S_2;SqStack S_3;//检测栈InitStack(S_1);//初始化堆栈InitStack(S_2);InitStack(S_3);SqQueue Q_1;SqQueue Q_2;InitQueue(Q_1);//初始化队列InitQueue(Q_2);printf("请输入魔王的语言:\n");scanf("%s",&MoWang);//将魔王语言存入数组中length=strlen(MoWang);//魔王语言的长度包括括号i=0;InStack(MoWang,S_1);//将魔王语言自右向左入栈InStack(MoWang,S_3);//检测魔王语言while(!StackEmpty(S_3)){Pop(S_3,j);if(j=='('){mark=1;}}if(mark==1){while(e!=')'){//处理")"之前的元素Pop(S_1,e);if(e=='('){Pop(S_1,str);//记录需要重复打印的字符while(e!=')'){Pop(S_1,e);EnQueue(Q_2,e);//将括号内的元素入队列i++;}break;}EnQueue(Q_1,e);//将"("外的元素存入第一个队列中}for(;i>2;i--)//将括号内除了第一个和最后一个元素，其他元素连同第一个元素分次入栈{DeQueue(Q_2,e);//将队列中的第一个元素弹出存入ePush(S_2,e);//将e压入s_2中Push(S_2,str);//将str压入s_2中}DeQueue(Q_2,e);//将括号中的最后一个元素弹出存入ePush(S_2,e);//将e压入s_2中//将s_2堆栈中的元素弹出到队列Q_1中while(!StackEmpty(S_2)){Pop(S_2,e);EnQueue(Q_1,e);}while(!StackEmpty(S_1))//将魔王语言")"后的读入到Q_1中{Pop(S_1,e);EnQueue(Q_1,e);}}else{//若无括号直接输入while(!StackEmpty(S_1)){Pop(S_1,e);EnQueue(Q_1,e);}}while(Q_1.front!=Q_1.rear){DeQueue(Q_1,e); //删除队首元素switch(e) //判断并打印翻译后的语言{case 't': printf("天");break;case 'd': printf("地");break;case 's': printf("上");break;case 'a': printf("一只");break;case 'w': printf(",");break;case 'e': printf("鹅");break;case 'z': printf("追");break;case 'g': printf("赶");break;case 'x': printf("下");break;case 'n': printf("蛋");break;case 'i': printf("恨");break;case 'A': printf("上一只鹅");break;case 'B': printf("天上一只鹅地上一只鹅");break;default: printf("error!!!");}}printf("\n"); //换行DestroyQueue(Q_1);DestroyQueue(Q_2); //释放队列qDestroyStack(S_1); //释放栈s DestroyStack(S_2);return 0;}5.测试结果翻译成功结果如下图：实验结论得分成功利用堆栈和数组完成魔王语言的翻译教师评价总分实际得分。