栈基本操作（顺序栈、共享栈、单链栈说明）C语言版

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 50
typedef struct
{
int *data;
int pop;
}Sqstack;
void Init(Sqstack *S)
//初始化栈
{
S->pop=-1;
printf("-------初始化成功");
}
int StackEmpty(Sqstack S) //判空
{
if(S.pop==-1)
return 1;
return -1;
}
int Length(Sqstack S)
//求栈长
{
return S.pop+1;
}
int Push(Sqstack *S,int d)
//压栈
{
if(S->pop>=MAXSIZE-1)
//判断栈满
return -1;
S->data[++S->pop]=d;
return 1;
}
int Pop(Sqstack *S)
//出栈
{
if(S->pop==-1)
return -1;
return S->data[S->pop--];
}
int GetTop(Sqstack S)
//读取第一个数据
{
if(S.pop==-1)
return -1;
return S.data[S.pop];
}
//-------------------------------------------以下为共享栈
typedef struct
{
int *data;
int front,rear; //定义两个游标，分别指向栈顶前一个和栈底后一个位置
}ShareStack;
void Init_S(ShareStack *S)
//初始化共享栈，其实就是把一个顺序栈分为分别以顶和底为栈底的两个站
{
S->front=-1;
S->rear=MAXSIZE;
printf("n--------共享栈初始化成功");
}
int Full_S(ShareStack S)
//判满
{
if(S.front+1==S.rear)
return 1;
return -1;
}
int Empty_S(ShareStack S)
//判空
{
if(S.front==-1&&S.rear==MAXSIZE)
//全空
return -1;
if(S.front==-1&&S.rear!=MAXSIZE)
//1号空
return -2;
if(S.front!=-1&&S.rear==MAXSIZE)
//2号空
return -3;
}
int Length_S(ShareStack S)
//求长
{
return S.front+1+MAXSIZE-S.rear;
}
int Push_S(ShareStack *S,int d,int SN)
//压栈
{
if(Empty_S(*S)==1) //若栈满
return -1;
if(SN!=1&&SN!=2)
//栈号判误
return -3;
if(SN==1)
S->data[++S->front]=d;
else
S->data[--S->rear]=d;
}
int Pop_S(ShareStack *S,int SN)
//出栈
{
if(SN!=1&&SN!=2)
//栈号判误
return -3;
if(SN==1)
{
if(Empty_S(*S)==-2) //若1号空
return -1;
return S->data[S->front--];
}
if(Empty_S(*S)==-3) //若2号空
return -2;
return S->data[S->rear++];
}
int Get_S(ShareStack *S,int SN) //读栈顶元素，与出栈区别为游标是否移动
{
if(SN!=1&&SN!=2)
//栈号判误
return -3;
if(SN==1)
{
if(Empty_S(*S)==-2) //若1号空
return -1;
return S->data[S->front];
}
if(Empty_S(*S)==-3) //若2号空
return -2;
return S->data[S->rear];
}
int main()
{
//----------------------以下为顺序栈
Sqstack S1;
S1.data=(int *)malloc(sizeof(int)*MAXSIZE);
Init(&S1);
printf("n是否为空：%d",StackEmpty(S1));
Push(&S1,2);
printf("n栈长：%d",Length(S1));
printf("n读取元素：%d",GetTop(S1));
printf("n弹出数据：%d",Pop(&S1));
printf("n栈长：%d",Length(S1));
free(S1.data);
//----------------------以下为共享栈
ShareStack S2;
S2.data=(int *)malloc(sizeof(int)*MAXSIZE);
Init_S(&S2);
printf("n共享栈长：%d",Length_S(S2));
Push_S(&S2,1,1);
Push_S(&S2,1,2);
printf("n共享栈长：%d",Length_S(S2));
Pop_S(&S2,1);
printf("n共享栈长：%d",Length_S(S2));
printf("n获取元素：%d",Get_S(&S2,2));
printf("n共享栈判空：%d",Empty_S(S2));
//----------------------以下为单链栈说明
/*单链栈操作逻辑与顺序栈一致，即压栈以头插法完成
（实际认为栈顶节点为头结点，即栈顶为头结点，所有操作都在表头进行）
出栈读出表头节点即头结点后继节点后将其删除，其他操作逻辑类比顺序栈*/
return 0;
}