栈
顺序栈
栈的操作只能在栈顶进行入栈出栈 后进先出
栈为空时 栈顶指针top为-1
n个不同元素进栈 出栈序列的个数为$\frac{1}{n+1}C_{2n}^{n}$ 卡特兰(Catalan)数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
using namespace std;
typedef char ElemType;
typedef struct
{
ElemType data[Maxsize];
int top;//栈顶指针
}SqStack;
void InitStack(SqStack &S){//初始化
S.top=-1;
}
bool Push(SqStack &S,ElemType e)//入栈 在栈顶插入一个新的元素
{
if(S.top==Maxsize-1) return 0;//栈满
S.data[++S.top]=e; //栈顶指针先加1 再将元素存入
return 1;
}
int Pop(SqStack &S,ElemType &e)//出栈 将栈顶元素删除
{
if(S.top==-1) return 0;//栈空
e=S.data[S.top--];//先将元素输出 再将栈顶指针减1
return 1;
}
bool GetTop(SqStack S,ElemType &e){//取栈顶元素
if(S.top==-1) return 0;
e=S.data[S.top];
return 1;
}
int Show(SqStack S){//从栈顶遍历到栈底
int i;
for(i=S.top;i>=0;i--){
cout<<S.data[i]<<endl;
}
cout<<endl;
return 1;
}
|
主函数部分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| int main()
{
SqStack S;
int i,j,m,n;
ElemType e;
InitStack(S);
cout<<"请输入要入栈的元素个数"<<endl;
cin>>j;
for(int i=1;i<=j;i++)
{
cout<<"请输入入栈的元素"<<endl;
cin>>e;
Push(S,e);
}
cout<<"元素入栈成功"<<endl;
do
{
cout<<"请输入对应功能的数字： 1.入栈 2.出栈 3.取栈顶元素 4.从栈顶到栈底显示元素 "<<endl;
cin>>m;
switch(m)
{
case 1:
{
cout<<"请输入入栈的元素"<<endl;
cin>>e;
Push(S,e);
break;
}
case 2:
{
Pop(S,e);
cout<<"删除成功"<<endl;
break;
}
case 3:
{
ElemType a;
GetTop(S,a);
cout<<"栈顶元素是"<<a<<endl;
break;
}
case 4:
{
cout<<"从栈顶到栈底显示元素"<<endl;
Show(S);
break;
}
}
cout<<"是否继续执行操作 1.继续 2.退出"<<endl;
cin>>n;
}while(n==1);
return 0;
}
|
共享栈
两个顺序栈S1 S2共享一个一维数据空间 两个栈的栈底分别设置为共享空间的两端
S1.top=-1时 栈S1为空 S2.top=Maxsize时 栈S2为空
两个栈顶指针相邻S2.top-S1.top=1时 两个栈满
共享栈能更有效的利用存储空间 降低发生上溢的可能
链栈
便于多个栈共享存储空间提高效率 并且不会存在栈满上溢的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
using namespace std;
typedef char ElemType;
typedef struct LinkNode
{
ElemType data;
struct LinkNode *next;
}*LiStack;
bool InitStack(LiStack &S)//链栈初始化
{
S=NULL;//S始终指向栈顶元素
return 1;
}
bool Push(LiStack &S,ElemType e)//入栈
{
LinkNode *p =new LinkNode;
p->data=e;
p->next=S;
S=p;
return 1;
}
bool Pop(LiStack &S,ElemType &e)//出栈
{
LinkNode *p=new LinkNode;
if(S==NULL) return 0;//空栈
e=S->data;
p=S;
S=S->next;
delete p;
return 1;
}
bool GetTop(LiStack S)//取栈顶元素;
{
if(S!=NULL) cout<<S->data<<endl;
return 1;
}
void Show(LiStack &S)
{
LinkNode *p =S;//p代替S对栈进行从上到下的遍历
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
|
主函数部分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| int main()
{
LiStack S;
int i,j,m,n;
ElemType e;
if(!InitStack(S)) cout<<"链栈初始化失败"<<endl;
cout<<"请输入要入栈的元素个数"<<endl;
cin>>j;
for(int i=1;i<=j;i++)
{
cout<<"请输入入栈的元素"<<endl;
cin>>e;
Push(S,e);
}
cout<<"元素入栈成功"<<endl;
do
{
cout<<"请输入对应功能的数字： 1.入栈 2.出栈 3.取栈顶元素 4.从栈顶到栈底显示元素 "<<endl;
cin>>m;
switch(m)
{
case 1:
{
cout<<"请输入入栈的元素"<<endl;
cin>>e;
Push(S,e);
break;
}
case 2:
{
Pop(S,e);
break;
}
case 3:
{
cout<<"栈顶元素为"<<endl;
GetTop(S);
break;
}
case 4:
{
cout<<"栈顶到栈底的元素依次为"<<endl;
Show(S);
break;
}
}
cout<<"是否继续执行操作 1.继续 2.退出"<<endl;
cin>>n;
}while(n==1);
}
|
