栈的顺序存储结构

顺序栈的实现

栈的顺序存储类型可描述为:

1
2
3
4
5
#define MaxSize 50				//定义栈中元素的最大个数
typedef struct{
ElemType data[MaxSize]; //存放栈中元素
int top; //栈顶指针
}SqStack;

顺序栈的基本运算

初始化

1
2
3
void InitStack(SqStack &s){
s.top=-1; //初始化栈顶指针
}

判栈空

1
2
3
4
5
6
bool StackEmpty(SqStack S){
if(s.top == -1) //栈空
return true;
else //不空
return false;
}

进栈

1
2
3
4
5
6
bool Push(SqStack &s,ElemType x){
if(s.top == MaxSize-1) //栈满,报错
return false;
s.data[++s.top]=x; //指针先加1,在入栈
return true;
}

出栈

1
2
3
4
5
6
bool Pop(SqStack &s,ElemType &x){
if(s.top == -1) //栈空,报错
return false;
x=s.data[s.top--]; //先出栈,指针再减1
return true;
}

读栈顶元素

1
2
3
4
5
6
7
bool GetTop(SqStack s,ElemType &x)
{
if(s.top == -1 ) //栈空,报错
return false;
x=s.data[s.top]; //x记录栈顶元素
return true;
}

顺序栈的完整操作

程序源代码:

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
#define MaxSize 50 //定义栈中元素的最大个数
typedef struct{
ElemType data[MaxSize]; //存放栈中元素
int top; //栈顶指针
}SqStack;
void InitStack(SqStack &s){
s.top=-1; //初始化栈顶指针
}
bool StackEmpty(SqStack S){
if(S.top == -1) //栈空
return true;
else //不空
return false;
}
bool Push(SqStack &s,ElemType x){
if(s.top == MaxSize-1) //栈满,报错
return false;
s.data[++s.top]=x; //指针先加1,在入栈
return true;
}
bool Pop(SqStack &s,ElemType &x){
if(s.top == -1) //栈空,报错
return false;
x=s.data[s.top--]; //先出栈,指针再减1
return true;
}
bool GetTop(SqStack s,ElemType &x)
{
if(s.top == -1 ) //栈空,报错
return false;
x=s.data[s.top]; //x记录栈顶元素
return true;
}
void PrintSqStack(SqStack s) //遍历栈
{
int tmp = s.top;
while(tmp!=-1) //如果tmp==-1说明遍历结束
{
cout<<s.data[tmp--]<<" ";
}
cout<<endl;
}
int main()
{
SqStack s; //声明一个顺序栈
InitStack(s); //初始化一个顺序栈
for(int i=1;i<=5;i++)
{
Push(s,i); //入栈
}
PrintSqStack(s); //遍历
for(int i=1;i<=5;i++){ //为了对比GetTop和Pop操作
int x;
GetTop(s,x); //取栈顶元素
cout<<"这是GetTop操作,栈顶元素为"<<x<<endl;
cout<<"这是GetTop操作后的栈遍历:";
PrintSqStack(s);
Pop(s,x); //出栈
cout<<"这是Pop操作,出栈的元素为"<<x<<endl;
if(!StackEmpty(s))
{
cout<<"这是Pop操作后的栈遍历:";
PrintSqStack(s);
}else{
cout<<"此时栈空!"<<endl;
}

}
return 0;
}

程序输出:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
5 4 3 2 1
这是GetTop操作,栈顶元素为5
这是GetTop操作后的栈遍历:5 4 3 2 1
这是Pop操作,出栈的元素为5
这是Pop操作后的栈遍历:4 3 2 1
这是GetTop操作,栈顶元素为4
这是GetTop操作后的栈遍历:4 3 2 1
这是Pop操作,出栈的元素为4
这是Pop操作后的栈遍历:3 2 1
这是GetTop操作,栈顶元素为3
这是GetTop操作后的栈遍历:3 2 1
这是Pop操作,出栈的元素为3
这是Pop操作后的栈遍历:2 1
这是GetTop操作,栈顶元素为2
这是GetTop操作后的栈遍历:2 1
这是Pop操作,出栈的元素为2
这是Pop操作后的栈遍历:1
这是GetTop操作,栈顶元素为1
这是GetTop操作后的栈遍历:1
这是Pop操作,出栈的元素为1
此时栈空!

栈的链式存储结构

栈的链式存储类型可描述为

1
2
3
4
typedef struct Linknode{
ElemType data; //数据域
struct Linknode *next; //指针域
}*Linknode; //栈类型操作

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!