数据结构中栈的介绍
数据结构中栈的介绍
1.栈的概念
栈（Stack）是一种特殊的表，这种表只在表的一端进行插入和删除操作。允许插入和删除数据元素的这一端称为栈顶；而另一固定的一端称为栈底。不含任何元素的栈称为空栈。
栈的修改是按后进先出的原则进行的。栈又称为后进先出(Last In First Out)表，简称为LIFO表。
如图1所示：假设一个栈S中的元素为a n,a n-1,..,a1，则称a1为栈底元素，a n为栈顶元素。
图1 图 2
2.栈的存储与操作
由于栈是一个特殊的表，可以用一维数组来实现栈。同时设立指针t（称为栈顶指针）来指示栈顶元素的当前位置。
我们用一个数组s[1..m]来表示一个栈时，将栈底固定在数组的底部，即s[1]为最早入栈的元素，并让栈向数组上方(下标增大的方向)扩展。当t=0时，表示这个栈为一个空栈。当t=m时，表示这个栈已满。
可以用下列方式定义栈：
const
m=栈表目数的上限;
type
stack=array[1..m] of stype; {栈的数据类型}
var
s:stack;
t:integer; {栈顶指针}
进栈、出栈操作的过程和函数（假设栈元素的数据类型为整型）：
(1)进栈过程（push）
①若t≥m时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）；
②置t=t+1（栈指针加１，指向进栈地址）；
③S(t)=x，结束（x为新进栈的元素）；
procedure push(var s:stack; x:integer;var t:integer);
begin
if t=m then writeln('overflow')
else
begin
t:=t+1;s[t]:=x;
end
end;
(2)退栈函数（pop）
①若t≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈，空则下溢；不空则作②)；
②x=s(t)，（退栈后的元素赋给x）；
③t=t-1，结束（栈指针减１，指向栈顶）。
function pop(var s:stack;var t:integer):integer;
begin
if t=0 then writeln('underflow')
else
begin
pop:=s[t];t:=t-1;
end
end;
(3)读栈顶元素函数（top）
function top(var s:stack; t:integer):integer;
begin
if t=0 then writeln('underflow')
else
top:=s[t];
end;
3栈的应用举例
【例10-4】.设栈S的初始状态为空，元素a,b,c,d,e,f,g依次入栈，以下出栈序列不可能出现的是（）。
A.a,b,c,e,d,f,g
B.b,c,a,f,e,g,d
C.a,e,d,c,b,f,g
D.d,c,f,e,b,a,g
E.g,e,f,d,c,b,a
题解：此题可以采用模拟的方法，依次判断各个选项是否能出现。如A，每个元素依次进栈然后出栈，即得到此序列。再来看B，a,b进栈，然后b出栈，c进栈后出栈，a出栈，d，e，f进栈，f，e出栈，g进栈后出栈，d出栈，可以满足。依此类推，发现只有E不能满足，答案为E。
【例10-5】.如下图,有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5共五个车厢。其中每个车厢可以向左行走,也可以进入栈S让后面的车厢通过。现已知第一个到达出口的是3号车厢，请写出所有可能的到达出口的车厢排列总数。
出口←←
S↓
题解：首先必是1，2，3进栈，然后3出栈，此时栈中有元素1，2，未进栈元素有4，5。我们可以分情况讨论，由于2一定在1之前出栈，我们可以讨论4，5的出栈顺序，如下：(1)4先出栈：此时相当于4，5不经过栈直接到出口。相当于1，2，4，5四个数字的一个
/4=6（种）。
排列，2排在1前，4排在5前，共有种数4
4
(2)5先出栈：此时4和5的出栈顺序必连续，有以下三种排列：
5 4 2 1；2 5 4 1；2 1 5 4。
综上所述，总的排列数是9种。
【例1】计算后缀表达式
题目描述
数学上使用的是中缀表达式，在中缀表达式中需要使用括号来改变运算的优先级。
事实上我们可以用后缀表达式或前缀表达式，这两种表达式里就可以完全避免使用括号。后缀表达式：运算符放在两个运算对象之后。所有计算按运算符出现的顺序，由左而右进行。例如：3*(5-2)+7 对应的后缀表达式为3.5.2.- *7.+@
现有一后缀表达式，让你求表达式的值，已知运算符仅限于"+","-","*","/"四种运算。输入@表示表达式结束，’.’为操作数的结束符。如：后缀表达式3.5.2.- *7.+@的值为16。输入
一个后缀表达式，无需判错，“/”作为整除运算。
输出
后缀表达式的值，一个整数。
参考程序：
program ex10_6;
const
n=30;
type
stack=array[1..n] of integer;
var
s:stack;
a:string;
t,i,j,k,q:integer;
procedure push(var s:stack; x:integer;var top:integer);
begin
if top=n then writeln('overflow')
else
begin
top:=top+1;s[top]:=x;
end
end;
function pop(var s:stack;var top:integer):integer;
begin
if top=0 then writeln('underflow')
else
begin
pop:=s[top];top:=top-1;
end
end;
begin
i:=1; t:=0;
readln(a);
while a[i]<>'@' do
begin
case a[i] of
'0'..'9' :begin
k:=0;
repeat
k:=10*k+ord(a[i])-ord('0');
i:=i+1;
until a[i]='.' ;
push(s,k,t); {数字进栈}
end;
'+' : push(s,pop(s,t)+pop(s,t),t); {取栈首的两个数值相加}
'-' :begin
j:=pop(s,t);
push(s,pop(s,t)-j,t);
end;
'*' : push(s,pop(s,t)*pop(s,t),t); { 取栈首的两个数值相乘}
'/' :begin
j:=pop(s,t);
push(s,pop(s,t) div j,t);
end;
end;
i:=i+1;
end;
q:=pop(s,t); {最后栈中的元素即为答案}
writeln(q);
end.
【例2】背包问题
假设有n件质量为w1，w2，...，w n的物品和一个最多能装载总质量为T的背包，能否从这n件物品中选择若干件物品装入背包，使得被选物品的总质量恰好等于背包所能装载的最大质量，即w i1+w i2+...+w ik=T。若能，则背包问题有解，否则无解。
算法思想
首先将n件物品排成一列，依次选取；若装入某件物品后，背包内物品的总质量不超过背包最大装载质量时，则装入（进栈）；否则放弃这件物品的选择，选择下一件物品试探，直至装入的物品总和正好是背包的最大转载质量为止。这时我们称背包装满。
若装入若干物品的背包没有满，而且又无其他物品可以选入背包，说明已装入背包的物品中有不合格者，需从背包中取出最后装入的物品（退栈），然后在未装入的物品中挑选，重复此过程，直至装满背包（有解），或无物品可选（无解）为止。
具体实现
设用数组w[1..N]，stack[1..N]分别存放物品重量和已经装入背包（栈）的物品序号，tot表示背包的剩余最大装载量。每进栈一个物品，就从tot中减去该物品的质量,设i为待选物品序号,若tot-w[i]>=0，则该物品可选；若tot-w[i] < 0，则该物品不可选,且若I=n，则需退栈，若此时栈空，则说明无解。
参考程序：
program ex10_7;
var t,n,i:integer;
w,stack:array[1..100]of integer;
function knap(tot:integer):boolean;
var
i,top:integer;
begin
top:=0;
i:=1;
while (tot>0)and (i<=n)do
begin
if (tot-w[i]>=0)and(i<=n) then begin
top:=top+1;
stack[top]:=i;
tot:=tot-w[i];
end;
if tot=0 then exit(true){正好装满则返回true}
else begin
if (i=n)and(top>0)then{I=n时退栈}
begin
i:=stack[top];dec(top);
tot:=tot+w[i];
if (i=n)and(top>0) then
begin{如退栈后I=n，即退栈的元素是最后一个，则需再次退栈，因为此时已无法选择下一个物品}
i:=stack[top];
dec(top);
tot:=tot+w[i];
end;
end;
inc(i);
end;
end;
exit(false);
end;
begin
readln(t,n);
for i:=1 to n do read(w[i]);
if knap(t) then writeln('Yes')
else writeln('No');
end.
数据结构实验二_栈的基本操作
青岛理工大学课程实验报告
s->top=s->base; s->stacksize=stack_init_size; return 1; } int Push(sqstack *s,int e) { if(s->top-s->base>=s->stacksize) { s->base=(int *)realloc(s->base,(s->stacksize+stackincrement)*sizeof(int)); if(!s->base) return 0; s->top=s->base+s->stacksize; s->stacksize+=stackincrement; } *(s->top++)=e; return e; } int Pop(sqstack *s,int e) { if(s->top==s->base) return 0; e=*--s->top; return e; } int stackempty(sqstack *s) { if(s->top==s->base) { return 1; } else Push(s,n%flag); n=n/flag; } while(!stackempty(s)) { e=Pop(s,e); switch(e) { case 10: printf("A"); break; case 11: printf("B"); break; case 12: printf("C"); break; case 13: printf("D"); break; case 14: printf("E"); break; case 15: printf("F"); break; default: printf("%d",e); } } printf("\n"); return 0; } int main() { sqstack s; StackInit(&s); conversion(&s); return 0; }
数据结构中栈的介绍
数据结构中栈的介绍 1.栈的概念 栈（Stack）是一种特殊的表，这种表只在表的一端进行插入和删除操作。允许插入和删除数据元素的这一端称为栈顶；而另一固定的一端称为栈底。不含任何元素的栈称为空栈。 栈的修改是按后进先出的原则进行的。栈又称为后进先出(Last In First Out)表，简称为LIFO表。 如图1所示：假设一个栈S中的元素为a n,a n-1,..,a1，则称a1为栈底元素，a n为栈顶元素。 图1 图 2 2.栈的存储与操作 由于栈是一个特殊的表，可以用一维数组来实现栈。同时设立指针t（称为栈顶指针）来指示栈顶元素的当前位置。 我们用一个数组s[1..m]来表示一个栈时，将栈底固定在数组的底部，即s[1]为最早入栈的元素，并让栈向数组上方(下标增大的方向)扩展。当t=0时，表示这个栈为一个空栈。当t=m时，表示这个栈已满。 可以用下列方式定义栈： const m=栈表目数的上限; type stack=array[1..m] of stype; {栈的数据类型} var s:stack; t:integer; {栈顶指针} 进栈、出栈操作的过程和函数（假设栈元素的数据类型为整型）： (1)进栈过程（push） ①若t≥m时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）； ②置t=t+1（栈指针加１，指向进栈地址）； ③S(t)=x，结束（x为新进栈的元素）； procedure push(var s:stack; x:integer;var t:integer); begin if t=m then writeln('overflow') else begin
顺序栈的基本操作讲解
遼穿紳範大學上机实验报告 学院:计算机与信息技术学院 专 业 ： 计算机科学与技术（师 范） 课程名称：数据结构 实验题目：顺序栈的基本操作 班级序号：师范1班 学号:201421012731 学生姓名：邓雪 指导教师：杨红颖 完成时间：2015年12月25号 一、实验目的： 1 ?熟悉掌握栈的定义、结构及性质； 2. 能够实现创建一个顺序栈，熟练实现入栈、出栈等栈的基本操作； 3?了解和掌握栈的应用。 二、实验环境： Microsoft Visual C++ 6.0
三、实验内容及要求： 栈是一种特殊的线性表，逻辑结构和线性表相同，只是其运算规则有更多的限制，故又称为受限的线性表。 建立顺序栈，实现如下功能： 1. 建立一个顺序栈 2. 输出栈 3. 进栈 4. 退栈 5. 取栈顶元素 6. 清空栈 7. 判断栈是否为空 进行栈的基本操作时要注意栈”后进先出”的特性。 四、概要设计： 1、通过循环，由键盘输入一串数据。创建并初始化一个顺序栈。 2、编写实现相关功能函数，完成子函数模块如下。 3、调用子函数，实现菜单调用功能，完成顺序表的相关操作
五、代码： #include
数据结构_实验三_栈和队列及其应用
实验编号：3四川师大《数据结构》实验报告2016年10月29日 实验三栈与队列及其应用_ 一．实验目得及要求 （1）掌握栈与队列这两种特殊得线性表，熟悉它们得特性，在实际问题背景下灵活运用它们； （2）本实验训练得要点就是“栈”得观点及其典型用法； （3）掌握问题求解得状态表示及其递归算法，以及由递归程序到非递归程序得转化方法。 二．实验内容 （1）编程实现栈在两种存储结构中得基本操作（栈得初始化、判栈空、入栈、出栈等）； （2）应用栈得基本操作，实现数制转换（任意进制）； （3）编程实现队列在两种存储结构中得基本操作（队列得初始化、判队列空、入队列、出队列）； （4）利用栈实现任一个表达式中得语法检查（括号得匹配）。 （5）利用栈实现表达式得求值。 注：（1）～（3）必做，（4）～（5）选做。 三．主要仪器设备及软件 （1）PC机 （2）Dev C++ ,Visual C++, VS2010等 四．实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）编程实现栈在两种存储结构中得基本操作（栈得初始化、判栈空、入栈、出栈等）； A、顺序储存： ?代码部分： //Main、cpp: #include"SStack、h" int main() { SqStack S; SElemType e;
int elect=1; InitStack(S); cout << "已经创建一个存放字符型得栈" << endl; while (elect) { Muse(); cin >> elect; cout << endl; switch (elect) { case 1: cout << "input data:"; cin >> e; Push(S, e); break; case 2: if(Pop(S, e)) {cout << e <<" is pop"<< endl; } else{cout<<"blank"< 北京理工大学珠海学院实验报告 ZHUHAI CAMPAUS OF BEIJING INSTITUTE OF TECHNOLOGY 班级软件工程3班学号 150202102309姓名郭荣栋 指导教师余俊杰成绩 实验题目栈的实现与应用实验时间 一、实验目的、意义 （1）理解栈的特点，掌握栈的定义和基本操作。 （2）掌握进栈、出栈、清空栈运算的实现方法。 （3）熟练掌握顺序栈的操作及应用。 二、实验内容及要求 1.定义顺序栈，完成栈的基本操作：建空栈、入栈、出栈、取栈顶元素（参见教材45页）。 2. 调用栈的基本操作，将输入的十进制数转换成十六进制数。 3. 调用栈的基本操作，实现表达式求值，如输入3*（7-2）#，得到结果15。 三、实验结果及分析 （所输入的数据及相应的运行结果，运行结果要有提示信息，运行结果采用截图方式给出。） 四、程序清单(包含注释) 1、2. #include typedef int SElemType; typedef int Status; typedef struct{ SElemType *base; SElemType *top; int stacksize; }Sqstack; void StackTraverse(Sqstack S) { while (S.top != S.base) { cout << *(S.top-1) << endl; S.top--; } } Status InitStack(Sqstack &S){ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base){ exit(OVERFLOW); } 栈的应用 迷宫求解 任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出； 源代码： #include 第五次实验报告—— 顺序栈、链栈的插入和删除一需求分析 1、在演示程序中，出现的元素以数字出现定义为int型， 2、演示程序在计算机终端上，用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在终端上 3、顺序栈的程序执行的命令包括如下： （1）定义结构体 （2）顺序栈的初始化及创建 （3）元素的插入 （4）元素的删除 （5）顺序栈的打印结果 3、链栈的程序执行的命令包括如下： （1）定义结构体 （2）链栈的初始化及创建 （3）元素的插入 （4）元素的删除 （5）链栈的打印结果 二概要设计 1、顺序栈可能需要用到有序表的抽象数据类型定义： ADT List{ 数据对象:D={ai|ai∈ElemL, i=1,2,...,n, n≥0} 数据关系:R1={ Status Pop(SqStack &S) 操作结果：删除栈顶元素 }ADT List； 2、链栈可能需要用到有序表的抽象数据类型定义： ADT List{ 数据对象:D={ai|ai∈ElemL, i=1,2,...,n, n≥0} 数据关系:R1={ 《算法与数据结构》课程实验报告 一、实验目的 1.熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等，掌握栈 的基本操作在栈的顺序存储结构。 2.实现栈的顺序存储结构,通过实验深入理解栈的操作特点。 二、实验内容及要求 1.实现栈的存储结构及相关操作：进栈、出栈、取栈顶元素等。 2.使用该栈完成对一个字符串的逆序输出。 3.使用该栈完成判断表达式的括号是否匹配。 4.对算术表达式求值。 三、系统分析 （1）数据方面：该栈数据元素类型采用浮点型，在此基础上进行栈的基本操作，并可将栈中数据使用文本文档保存。在栈的应用中，采用的是存储字符元素类型的栈，并进行对字符的相关操作。 （2）功能方面：能实现栈的一些基本操作，主要包括： 1.进栈操作：若栈不满，则将元素x插入至栈的栈顶，若栈满则进行溢出 处理。 2.出栈操作：若栈不空，则函数返回该栈栈顶的元素，并且栈顶指针退1。 3.获取栈顶元素：若栈不空，则函数返回栈顶元素。 4.判断栈是否为空、判断栈是否满。 5.计算栈中元素个数：直接返回栈中元素个数。 6.清空栈内容：将栈顶指针赋为初始值。 7.保存数据：将栈中元素数据保存至文本文档中。 四、系统设计 （1）设计的主要思路 顺序栈可以采用顺序表作为其存储表示，为此，在顺序栈的声明中用顺序表定义它的存储空间。存放栈元素的数组的头指针为*elements，该数组最大能允许存放元素个数为maxSize，当前栈顶位置由数组下标指针top知识。并规定如果栈不空时，elements[0]为栈中第一个元素。由于实验中还需完成栈的相关应用，故使用两个菜单分别完成栈的基本操作与栈的应用调试。 （2）数据结构的设计 顺序栈定义为只允许在表的末端进行插入和删除的线性表。允许插入和删除的一端叫做栈顶，而不允许插入和删除的另一端叫做栈底。当栈中没有任何元素时则成为空战。即栈又被称为后进先出的线性表，故与线性表的相关操作类似， 《数据结构》实验报告 实验序号：4 实验项目名称：栈的操作 } 改写以上程序，实现功能如下： 调用栈操作函数实现判别一个算术表达式中的圆括号和方括号配对是否正确匹配。 2.C/C++的库函数中已经实现了栈，实例如下： #include 对上机实践结果进行分析，上机的心得体会。 五、教师评语 成绩 签名： 日期： 附源程序清单： 1. #include if(st->top==MaxSize-1) { printf("栈上溢出!\n"); } else { st->top++; //移动栈顶位置 st->data[st->top]=x; //元素进栈 } } void Pop(SqStack *st,ElemType *e) //出栈 { if(st->top==-1) { printf("栈下溢出\n"); } else { *e=st->data[st->top]; //元素出栈 st->top--; //移动栈顶位置 } } int main() { SqStack L; SqStack *st=&L; ElemType e,a[MaxSize]; int i,j=1,k; do{ InitStack(st); gets(a); for(i=0;a[i]!='\0';i++) { if(a[i]=='('||a[i]=='{'||a[i]=='[') //左括号入栈Push(st,a[i]); if(a[i]==')') { if(StackEmpty(st) ==1)//判断栈是否为空 { printf("多了“(”，不匹配\n"); break; } #include 利用栈实现递归参考程序1（Turbo2.0环境）： #define MAXSIZE 100 #include printf("%d",k); else printf("%c",k+55); } printf("\n"); } main(){ int num; clrscr(); printf("Input a num,-1 to quit:\n"); scanf("%d",&num); while(num!=-1){ trans(num); scanf("%d",&num); } } 参考程序2：（C＋＋/VC环境） #define STACK_INIT_SIZE 100//存储空间初始分配量 #define OVERFLOW -1 #define OK 1 #define STACKINCREMENT 10//存储空间分配增量 #define ERROR 0 #define TRUE 1 #define FALSE 0 #include "stdio.h" #include "stdlib.h" #include "malloc.h" #include "iostream.h" typedef int status; typedef char SElemType; typedef struct{//顺序栈的定义 SElemType *base; SElemType *top; int stacksize; }SqStack; status InitStack(SqStack &S){//构造一个空栈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; } 实验名称栈的基本操作 实验目的 掌握栈这种抽象数据类型的特点及实现方法。 实验内容 从键盘读入若干个整数，建一个顺序栈或链式栈，并完成下列操作： （1）初始化栈； （2）判栈为空； （3）出栈； （4）入栈。 算法设计分析 （一）数据结构的定义 struct stackNode{ int data; struct stackNode *nextPtr; }; typedef struct stackNode listStact; typedef listStact *stackNodePtr; （二）总体设计 程序由主函数、入栈函数，出栈函数，删除函数判官是否为空函数和菜单函数组成。 （1）主函数：调用各个函数以实现相应功能 （三）各函数的详细设计： Function1: void instruct() //菜单 （1）：使用菜单显示要进行的函数功能； Function2：void printStack(stackNodePtr sPtr) //输出栈 （1）：利用if判断栈是否为空； （2）：在else内套用while（头指针不为空条件循环）循环输出栈元素； Function3：void push(stackNodePtr *topPtr,int value //进栈 （1）：建新的头指针； （2）：申请空间； （3）：利用if判断newPtr不为空时循环进栈 （4）：把输入的value赋值给newPtr，在赋值给topPtr，再指向下一个位置； Function4：int pop(stackNodePtr*topPtr) //删除 （1）：建新的头指针newPtr； （2）：利用if判断newPtr是否为空，再删除元素。 （3）：把topPtr等于newPtr，把头指针指向的数据赋值给topValue，输出要删除的数据值，头指针指向下一个位置，并清空newPtr； （4）：完成上述步骤后，return toPvalue，返回； 数据结构实验三 课程数据结构实验名称顺序栈基本操作第页 专业班级学号 姓名 实验日期：年月日评分 一、实验目的 1．熟悉并能实现栈的定义和基本操作。 2．了解和掌握栈的应用。 二、实验要求 1．进行栈的基本操作时要注意栈"后进先出"的特性。 2．编写完整程序完成下面的实验内容并上机运行。 3．整理并上交实验报告。 三、实验内容 1．编写程序任意输入栈长度和栈中的元素值，构造一个顺序栈，对其进行清空、销毁、入栈、出栈以及取栈顶元素操作。 2．编写程序实现表达式求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。 主要功能描述如下： （1）从键盘上输入表达式。 （2）分析该表达式是否合法： ?a) 是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中。 ?b) 是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值。 ?c) 若是其它字符，则返回错误信息。 （3）若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。 程序中应主要包含下面几个功能函数： ?l void initstack()：初始化堆栈 ?l int Make_str()：语法检查并计算 ?l int push_operate(int operate)：将操作码压入堆栈 ?l int push_num(double num)：将操作数压入堆栈 ?l int procede(int operate)：处理操作码 ?l int change_opnd(int operate)：将字符型操作码转换成优先级 ?l int push_opnd(int operate)：将操作码压入堆栈 ?l int pop_opnd()：将操作码弹出堆栈 ?l int caculate(int cur_opnd)：简单计算+，-，*，/ ?l double pop_num()：弹出操作数 四、实验步骤 （描述实验步骤及中间的结果或现象。在实验中做了什么事情，怎么做的，发生的现象和中间结果） 第一题： #include 数据结构用栈实现背包问题 #include 第一章栈 【上机练习】 1、表达式括号匹配(stack) 【问题描述】 假设一个表达式有英文字母（小写）、运算符（+，—，*，/）和左右小（圆）括号构成，以“@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YES”；否则返回“NO”。表达式长度小于255，左圆括号少于20个。 【输入文件】 输入文件stack.in包括一行数据，即表达式， 【输出文件】 输出文件stack.out包括一行，即“YES”或“NO”。 【输入输出样例】 【样例输入1】【样例输出1】【样例输入2】【样例输出2】 2*(x+y)/(1-x)@YES(25+x)*(a*(a+b+b)@NO 2、括弧匹配检验(check) 【问题描述】 假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，如（［］（））或［（［］［］）］等为正确的匹配，［（］）或（［］（）或( ( ) ) ）均为错误的匹配。 现在的问题是，要求检验一个给定表达式中的括弧是否正确匹配？ 输入一个只包含圆括号和方括号的字符串，判断字符串中的括号是否匹配，匹配就输出“OK” ，不匹配就输出“Wrong”。输入一个字符串：［（［］［］）］，输出：OK 【输入格式】 输入仅一行字符（字符个数小于255） 【输出格式】 匹配就输出 “OK” ，不匹配就输出“Wrong”。 【输入样例】 ［（］） 【输出样例】 Wrong 3、字符串匹配问题(strs) 【问题描述】 字符串中只含有括号 (),[],<>,{},判断输入的字符串中括号是否匹配。如果括号有互相包含的形式，从内到外必须是<>,(),[],{}，例如。输入: [()] 输出:YES，而输入([])，([)]都应该输出NO。 【输入格式】 文件的第一行为一个整数n，表示以下有多少个由括好组成的字符串。接下来的n行，每行都是一个由括号组成的长度不超过255的字符串。 【输出格式】 在输出文件中有n行，每行都是YES或NO。 第3章栈 3.1 知识点分析 1．栈的基本概念 （1）栈是一种特殊的、只能在表的一端进行插入或删除操作的线性表。允许插入、删除的一端称为栈顶，另一端称为栈底。 （2）栈的逻辑结构和线性表相同，其最大特点是“后进先出”。 （3）栈的存储结构有顺序栈和链栈之分，要求掌握栈的C语言描述方法。 （4）重点掌握在顺序栈和链栈上实现：进栈、出栈、读栈顶元素、判栈空和判栈满等基本操作。 （5）熟悉栈在计算机的软件设计中的典型应用，能灵活应用栈的基本原理解决一些实际应用问题。 2．顺序栈 顺序栈是利用地址连续的存储单元依次存放从栈底到栈顶的元素，同时附设栈顶指针来指示栈顶元素在栈中的位置。 （1）用一维数组实现顺序栈 设栈中的数据元素的类型是字符型，用一个足够长度的一维数组s来存放元素，数组的最大容量为MAXLEN，栈顶指针为top，则顺序栈可以用C（或C++）语言描述如下：#define MAXLEN 10 // 分配最大的栈空间 char s[MAXLEN]；// 数据类型为字符型 int top；// 定义栈顶指针 （2）用结构体数组实现顺序栈 顺序栈的结构体描述： #define MAXLEN 10 // 分配最大的栈空间 typedef struct // 定义结构体 { datatype data[MAXLEN]；// datatype可根据用需要定义类型 int top；// 定义栈顶指针 }SeqStack； SeqStack *s；// 定义S为结构体类型的指针变量 （3）基本操作的实现要点 (a）顺序栈进栈之前必须判栈是否为满，判断的条件：s->top==MAXLEN–1。 (b）顺序栈出栈之前必须判栈是否为空，判断的条件：s->top==–1。 (c）初始化栈（置栈空）：s->top==–1。 (d）进栈操作： if （s->top!=MAXLEN–1）// 如果栈不满 { s->top++；// 指针加1 s->data[s->top]=x；// 元素x进栈 } (e）出栈操作： if （s->top!=–1）// 如果栈不空 { *x=s->data[s->top]；// 出栈（即栈顶元素存入*x） s->top––；// 指针加1 } (f）读栈顶元素 if （s->top!=–1）// 如果栈不空 return(s->data[s->top])；// 读栈顶元素，但指针未移动 第三章习题 一、基本题 1．填空：线性表、栈和队列都是_____结构，可以在线性表的_____位置插入和删除元素，对于栈只能在_______位置插入和删除元素，对于队只能在______位置插入和______位置删除元素。 2. 栈和队列数据结构的特点，什么情况下用到栈，什么情况下用到队列？ 3．设有编号为1，2，3，4的四辆车，顺序进入一个栈式结构的站台，试写出这四辆车开出车站的所有可能的顺序（每辆车可能入站，可能不入站，时间也可能不等）。 4．试证明：若借助栈由输入序列1，2，…，n得到输出序列为p1p2…p n (它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i 实验二栈和队列的基本操作实现及其应用 一、实验目的 1、熟练掌握栈和队列的基本操作在两种存储结构上的实现。 2、会用栈和队列解决简单的实际问题。 二、实验内容（可任选或全做） 题目一、试写一个算法，判断依次读入的一个以@为结束符的字符序列， 是否为回文。所谓“回文“是指正向读和反向读都一样的一字符串,如“321123”或“ableelba”。 相关常量及结构定义： # define STACK_INIT_SIZE 100 # define STACKINCREMENT 10 # define OK 1 # define ERROR 0 typedef int SElemType; //栈类型定义 typedef struct SqStack { SElemType *base; SElemType *top; int stacksize; }SqStack; 设计相关函数声明： 判断函数：int IsReverse() 栈：int InitStack(SqStack &S ) int Push(SqStack &S, SElemType e ) int Pop(SqStack &S,SElemType &e) int StackEmpty(s) 题目二、编程模拟队列的管理，主要包括： 出队列、 入队、 统计队列的长度、 查找队列某个元素e、 及输出队列中元素。 [实现提示]：参考教材循环队列的有关算法，其中后两个算法参考顺序表的实现。 题目三、Rails Description There is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds were extremely limited that time. It was possible to establish only a surface track. Moreover, it turned out that the station could be only a dead-end one (see picture) and due to lack of available space it could have only one track. The local tradition is that every train arriving from the direction A continues in the direction B with coaches reorganized in some way. Assume that the train arriving from the direction A has N <= 1000 coaches numbered in increasing order 1, 2, ..., N. The chief for train reorganizations must know whether it is possible to marshal coaches continuing in the direction B so that their order will be a1, a2, ..., aN. Help him and write a program that decides whether it is possible to get the required order of coaches. You can assume that single coaches can be disconnected from the train before they enter the station and that they can move themselves until they are on the track in the direction B. You can also suppose that at any time there can be located as many coaches as necessary in the station. But once a coach has entered the station it cannot return to the track in the direction A and also once it has left the station in the direction B it cannot return back to the station. Input The input consists of blocks of lines. Each block except the last describes one train and possibly more requirements for its reorganization. In the first line of the block there is the integer N described above. In each of the next lines of the block there is a permutation of 1, 2, ..., N. The last line of the block contains just 0. The last block consists of just one line containing 0. Output数据结构栈的定义及基本操作介绍
数据结构栈的应用(迷宫求解)
数据结构栈的基本操作,进栈,出栈
数据结构实验—栈及其应用
数据结构栈的应用
数据结构——顺序栈的基本操作
数据结构利用栈实现递归
数据结构(C语言)栈的基本操作
(完整word版)顺序栈基本操作实验报告
数据结构 用栈 实现 背包问题
数据结构 栈
数据结构答案第3章栈学习指导
栈和队列数据结构的特点
数据结构 栈和队列的基本操作实现及其应用
- 第三章栈和队列习题_数据结构(推荐文档)
- 数据结构_实验三_栈和队列及其应用
- 数据结构C语言版_栈的顺序存储表示和实现
- 利用栈实现表达式求解课件
- 数据结构实验二题目一栈和队列实验报告
- 栈和队列习题_数据结构
- 数据结构-栈代码
- 数据结构堆栈实验报告doc
- 数据结构练习题第三章栈、队列和数组习题及答案
- 数据结构利用栈实现递归
- 栈的表示和实现 数据结构
- 数据结构实验三 顺序栈的实现
- 数据结构栈与队列C语言实现
- 数据结构实验三栈的实现
- 数据结构中栈的介绍
- 数据结构中栈的介绍
- 数据结构栈和队列实验报告
- 数据结构栈实验
- 数据结构C语言版_栈实现表达式求值
- 长沙理工大学数据结构栈的实现及应用算术表达式求值实验报告