【数据结构】实验五：栈

实验五  栈

一、实验目的与要求

1）熟悉栈的类型定义和基本操作；

2）灵活应用栈解决具体应用问题。

二、实验内容

1、判断回文数，回文是指正读反读均相同的字符序列，如“1221”和“12321”均是回文，但“1234”不是回文。请写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)

2、给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串s ，判断字符串是否有效。有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

示列："()"和"()[]{}"都是合法的括号序列，但"( ]"和"( [ )]"不合法。

3、在某程序中，有两个栈共享一个一维数组空间SPACE[N]，SPACE[0]、SPACE[N-1] 分别是两个栈的栈底。(扩展选作)

  （1）对栈1、栈2，试分别写出（元素x）入栈的主要语句和出栈的主要语句。

  （2）对栈1、栈2，试分别写出栈满、栈空的条件。

三、实验结果

1）请将调试通过的源代码粘贴在下面。（代码注意书写规范、主要模块要有功能注释）

实验1代码：

#include <iostream>
#include <cstring>
using namespace std;
typedef struct{char data[1000];int top;
}Stack;//初始化栈 
void Init_stack(Stack *s){s->top=-1;
}//元素入栈 
void Push_stack(Stack *s,char x){s->top=s->top+1;s->data[s->top]=x;
}//元素出栈 
void Pop_stack(Stack *s,char *x){*x=s->data[s->top];s->top=s->top-1;
}int main(){char data[1000],x;int i;Stack s;//初始化测试栈 Init_stack(&s);cin>>data;//输入的字符串长度 int len=strlen(data);//输入的字符串入栈 for(i=0;i<len;i++){Push_stack(&s,data[i]);}//首尾对比，判断回文数 for(i=0;i<len;i++){Pop_stack(&s,&x);if(data[i]!=x){cout<<"不是回文数"<<endl;return 0;}}cout<<"是回文数"<<endl;return 0;
}

实验1结果展示：

 

 

 

 实验2代码：

#include <iostream>
#include <cstring>
using namespace std;typedef struct{char data[1000];//元素 int top;//顶指针 
}Stack;//初始化栈 
void Init_stack(Stack *s){s->top=-1;
}//元素入栈 
void Push_stack(Stack *s,char *x){s->top=s->top+1;s->data[s->top]=*x;
}//元素出栈 
void Pop_stack(Stack *s,char *x){*x=s->data[s->top];s->top=s->top-1;
}int main(){char str[1000];Stack s;Init_stack(&s);cout<<"Please input your string：";cin>>str;int len=strlen(str),i=0;//len为str的长度 //cout<<len;//如果长度为奇数，一定缺少括号 if(len%2!=0){cout<<"Wrong string!"<<endl;return 0;}//长度为偶数，分类讨论 for(i=0;i<len;i++){//[]情况 if(str[i]=='['){Push_stack(&s,&str[i]);if(str[i+1]==']'){Pop_stack(&s,&str[i]);continue;}else{cout<<"Wrong string!"<<endl;return 0;}}//()情况 if(str[i]=='('){Push_stack(&s,&str[i]);if(str[i+1]==')'){Pop_stack(&s,&str[i]);continue;}else{cout<<"Wrong string!"<<endl;return 0;}}//{}情况 if(str[i]=='{'){Push_stack(&s,&str[i]);if(str[i+1]=='}'){Pop_stack(&s,&str[i]);continue;}else{cout<<"Wrong string!"<<endl;return 0;}}}cout<<"Right string!"<<endl; return 0;
}

实验2结果展示：

 

 

 

 

 实验3代码：

#include <cstdio>
#define MaxSize 10 //栈的容量 
#define ElemType int
#include <iostream>
using namespace std;			typedef struct {ElemType data[MaxSize];		int top1;//1号栈栈顶指针int top2;//2号栈栈顶指针
}ShStack;//初始化共享栈
void InitShStack(ShStack& S) {S.top1 = -1;//初始化1号栈栈顶指针S.top2 = MaxSize;//初始化2号栈栈顶指针
}//1号栈判空
bool Stack1Empty(ShStack S) {return (S.top1 == -1);
}//2号栈判空
bool Stack2Empty(ShStack S) {return (S.top2 == MaxSize);
}//1号栈入栈操作：新元素入栈(先存再加)
bool Push1(ShStack& S, ElemType x) {if (S.top1+1 == S.top2){return false;//栈满，报错}S.data[++S.top1] = x;return true;
}//2号栈入栈操作：新元素入栈(先存再加)
bool Push2(ShStack& S, ElemType x) {if (S.top1+1 == S.top2){return false;//栈满，报错}S.data[--S.top2] = x;return true;
}//1号栈出栈操作：栈顶元素出栈
bool Pop1(ShStack& S, ElemType& x) {if (S.top1 == -1){return false;//1号栈栈空，报错}x = S.data[S.top1--];	return true;
}//2号栈出栈操作：栈顶元素出栈
bool Pop2(ShStack& S, ElemType& x) {if (S.top2 == MaxSize){return false;//2号栈栈空，报错}x = S.data[S.top2++];return true;
}//1号栈读取栈顶元素操作
bool GetTop1(ShStack S, ElemType& x) {if (S.top1 == -1){return false;//1号栈栈空，报错}x = S.data[S.top1];return true;
}//2号栈读取栈顶元素操作
bool GetTop2(ShStack S, ElemType& x) {if (S.top2 == MaxSize){return false;//2号栈栈空，报错}x = S.data[S.top2];return true;
}int main() {//声明一个共享栈ShStack S;		//初始化共享栈InitShStack(S);//1号栈-判空if(Stack1Empty(S)){printf("当前1号栈空！\n");}else{printf("当前1号栈非空！\n");}//1号栈-入栈操作ElemType e1;printf("请输入1号栈入栈元素的值：");scanf("%d", &e1);if(Push1(S, e1)){printf("1号栈新元素入栈成功！\n");}else{printf("共享栈已满,1号栈新元素入栈失败！\n");}//1号栈-读取栈顶元素ElemType e2 = -1;if(GetTop1(S, e2)){printf("1号栈读取栈顶元素成功，当前栈顶元素值为：%d\n", e2);}else{printf("1号栈已空，读取栈顶元素失败！\n");}//1号栈-出栈操作ElemType e3 = -1;if(Pop1(S, e3)){printf("1号栈栈顶元素出栈成功，出栈元素值为：%d\n", e3);}else{printf("1号栈已空，栈顶元素出栈失败！\n");}//1号栈-读取栈顶元素ElemType e4 = -1;if (GetTop1(S, e4))printf("1号栈读取栈顶元素成功，当前栈顶元素值为：%d\n", e4);elseprintf("1号栈已空，读取栈顶元素失败！\n");cout<<endl;//2号栈-判空if (Stack2Empty(S)){printf("当前2号栈空！\n");}else{printf("当前2号栈非空！\n");}//2号栈-入栈操作ElemType e21;printf("请输入2号栈入栈元素的值：");scanf("%d", &e21);if (Push2(S, e21)){printf("2号栈新元素入栈成功！\n");}else{printf("共享栈已满,2号栈新元素入栈失败！\n");}//2号栈-读取栈顶元素ElemType e22 = -1;if (GetTop2(S, e22)){printf("2号栈读取栈顶元素成功，当前栈顶元素值为：%d\n", e22);}else{printf("2号栈已空，读取栈顶元素失败！\n");}//2号栈-出栈操作ElemType e23 = -1;if (Pop2(S, e23)){printf("2号栈栈顶元素出栈成功，出栈元素值为：%d\n", e23);}else{printf("2号栈已空，栈顶元素出栈失败！\n");}//2号栈-读取栈顶元素ElemType e24 = -1;if (GetTop2(S, e24)){printf("2号栈读取栈顶元素成功，当前栈顶元素值为：%d\n", e24);}else{printf("2号栈已空，读取栈顶元素失败！\n");}return 0;
}

实验3结果展示：

 

---

2）请分析你程序中每个功能模块的算法时间复杂度。

实验1：

单元素出栈只需要锁定顶层的元素即可。所以，时间复杂度为O(1)。

单元素入栈只需要对顶层进行元素覆盖即可。所以，时间复杂度为O(1)。

假设字符串长度为len，那么多元素入栈需要执行len次。所以，时间复杂度为O(n)。

本段代码通过对入栈后的字符串反向出栈进行判断，即出栈的第一个元素是原来字符串的最后一个元素。我们可以令出栈的第一个元素与原字符串的第一个元素进行对比，来判断该字符串对应的数字是否为回文数。所以，时间复杂度为O(n)。

实验2：

出栈、入栈等操作沿用实验1的结果，这里不再赘述。

当输入的符号字符串长度为奇数的时候，一定有一个括号落单，即一定不可能为合法的输入。符号字符串的长度为偶数是必要不充分条件，因此直接否定奇数长度可减少算力。所以，时间复杂度为O(1)。

本段算法通过循环先对当前的字符进行判断，再对下一个邻近的字符进行判断，即判断相邻两个括号是否为合法输入。整个过程需要对字符串每一个位置的字符进行判断。所以，时间复杂度为O(n)。

实验3：

判断栈是否为空栈，只需要判断顶指针是否处于-1位置。所以，时间复杂度为O(1)。

新元素入栈的时候，先要判断共享栈是否已满。如果共享栈非满，那么在下一个位置插入一个元素，顶指针同时移动到该位置。所以，时间复杂度为O(1)。

新元素出栈的时候，先要判断共享栈是否已空。如果共享栈非空，那么在当前位置弹出一个元素，顶指针同时移动到前一个位置。所以，时间复杂度为O(1)。

查看共享栈的两个栈顶元素时，只需要在保证两个栈非空的情况下，对顶指针所指向的元素进行查看。所以，时间复杂度为O(1)。

---

其他：

#include<iostream>
#include<cstring>
#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10
using namespace std;typedef struct SqStack {char *elem;int top;int stacksize;
}SqStack;//初始化栈，容量是事先定义好的，定义初始的top标号为-1.
void InitStack(SqStack& S)
{S.elem = new char[STACK_INIT_SIZE];if (!S.elem)cout << "Overflow!" << endl;S.top = -1;S.stacksize = STACK_INIT_SIZE;
}//该函数用来释放栈的空间
void DestroyStack(SqStack& S)
{delete[]S.elem;S.top = -1;S.stacksize = 0;
}//若栈已满，该函数用来增加栈的空间
void increment(SqStack& S)
{char *newstack = new char[S.stacksize + STACK_INCREMENT];if (!newstack)cout << "Overflow!" << endl;for (int i = 0; i <= S.top; i++){newstack[i] = S.elem[i];}delete[]S.elem;S.elem = newstack;S.stacksize += STACK_INCREMENT;
}//该函数用来往栈里面增添元素，因为是入栈，所以栈顶元素的位置数加一，该元素成为新的栈顶元素
void Push(SqStack& S, char e)
{if (S.top == S.stacksize - 1)increment(S);S.elem[++S.top] = e;
}//该元素用来返回栈顶元素的值
char GetTopStack(SqStack& S)
{if (S.top == -1)cout << "Empty!" << endl;return S.elem[S.top];
}//该函数用来将元素出栈
void Pop(SqStack& S)
{if (S.top == -1)cout << "Empty!" << endl;S.top--;
}//主函数：将字符串的长度len对2取模记为mid，将前mid个字符入栈。若该字符串回文：先给标志赋值为0，如果len为偶数，则第mid+1个元素应和栈顶元素相同，如果不同就直接退出循环，将标志的值改为1；相同就将元素出栈，判断下一个字符和栈顶元素是否相等，以此类推。如果len为奇数，则最中间的元素和其它元素都不同，跳过这个元素继续向下判断。最后通过标志的值判断该字符串是否回文：如果标志的值被修改，说明对称的两元素不相同，则字符串不回文。
int main()
{SqStack s;InitStack(s);char str[1000];cin >> str;int len = strlen(str);int mid = len / 2;int i, flag = 0;for (i = 0; i < mid; i++){Push(s, str[i]);}if (len % 2 == 1)i++;while (i<len){if (GetTopStack(s) != str[i]){flag = 1;break;}i++;Pop(s);}if (flag){cout << "该字符向量不是回文！" << endl;}else{cout << "该字符向量是回文！" << endl;}return 0;
}

#include<iostream>
#include<cstring>
#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10
using namespace std;typedef struct SqStack {char* elem;int top;int stacksize;
}SqStack;//初始化栈，容量是事先定义好的，定义初始的top标号为-1.
void InitStack(SqStack& S)
{S.elem = new char[STACK_INIT_SIZE];if (!S.elem)cout << "Overflow!" << endl;S.top = -1;S.stacksize = STACK_INIT_SIZE;
}//该函数用来释放栈的空间
void DestroyStack(SqStack& S)
{delete[]S.elem;S.top = -1;S.stacksize = 0;
}//若栈已满，该函数用来增加栈的空间
void increment(SqStack& S)
{char* newstack = new char[S.stacksize + STACK_INCREMENT];if (!newstack)cout << "Overflow!" << endl;for (int i = 0; i <= S.top; i++){newstack[i] = S.elem[i];}delete[]S.elem;S.elem = newstack;S.stacksize += STACK_INCREMENT;
}//该函数用来往栈里面增添元素，因为是入栈，所以栈顶元素的位置数加一，该元素成为新的栈顶元素
void Push(SqStack& S, char e)
{if (S.top == S.stacksize - 1)increment(S);S.elem[++S.top] = e;
}//该元素用来返回栈顶元素的值
char GetTopStack(SqStack& S)
{if (S.top == -1)cout << "Empty!" << endl;return S.elem[S.top];
}//该函数用来将元素出栈
void Pop(SqStack& S)
{if (S.top == -1)cout << "Empty!" << endl;S.top--;
}//主函数：输入字符串，向后遍历，如果元素是左括号则将左括号入栈，如果元素是右括号，则将左括号弹出栈顶，这样可以继续判断下一个左括号是否和右括号匹配。一旦右括号和左括号匹配不成功，那么修改标志表示括号匹配失败。其中，需要一开始就将‘#’压入栈，如果最后字符串遍历完了（也就是左括号都被消解完了）栈顶元素是‘#’，说明左括号和右括号匹配上不多不少刚刚好。
int main()
{SqStack s;int flag = 1;InitStack(s);Push(s, '#');char str[1000];cin >> str;int len = strlen(str);for (int i = 0; i < len; i++){if (str[i] == '(' || str[i] == '[' || str[i] == '{')Push(s, str[i]);else{if (str[i] == ')'){if (GetTopStack(s) != '('){flag = 0;break;}elsePop(s);}else if (str[i] == ']'){if (GetTopStack(s) != '['){flag = 0;break;}elsePop(s);}else if (str[i] == '}'){if (GetTopStack(s) != '{'){flag = 0;break;}elsePop(s);}}}if (GetTopStack(s) != '#')flag = 0;if (flag)cout << "括号匹配成功！" << endl;elsecout << "括号匹配失败！" << endl;return 0;
}

设top1和top2分别为栈1和2的栈顶元素的位置。

(1) 入栈主要语句

栈1的入栈语句：

if(top2-top1==1)

{

cout<<“栈满”<<endl;

exit(0);

}

SPACE[++top1]=x; //设x为入栈元素。

栈2的入栈语句：

if(top2-top1==1)

{

cout<<“栈满”<<endl;

exit(0);

}

SPACE[--top2]=x;

出栈主要语句

栈1的出栈语句:

if(top1==-1)

{

cout<<“栈空”<<endl;

exit(0);

}

top1--;

return(SPACE[top1+1]); //返回出栈元素。

栈2的出栈语句:

if(top2==N)

{

cout<<“栈空”<<endl;

exit(0);

}

top2++;

return(SPACE[top2-1]);

1. 栈满条件:top2-top1=1

栈空条件:top1=-1并且top2=N //top1=-1为左栈空,top2=N为右栈空