8、数据结构——栈与队列——顺序栈(二)

结构体定义

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

初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
// 方式一(与后面的对应着的)
void InitStack(SqStack &S) {
S.top = -1;
}

// 方式二(与后面的对应着的)
void InitStack(SqStack &S) {
S.top = 0;
}
void testStack() {
SqStack S;
InitStack(S);
}

判栈空

1
2
3
4
5
6
7
8
9
10
// 方式一(与后面的对应着的)
bool Empty(SqStack &S) {
return S.top == -1;
}

// 方式二(与后面的对应着的)
bool Empty(SqStack &S) {
return S.top == 0;
}

进栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 方式一(与后面的对应着的)
bool Push(SqStack &S, ElemType x) {
if (S.top == MaxSize - 1) return false; // 判断是否栈满

S.top = S.top + 1;
S.data[S.top] = x;
// 上面两条语句可以合并为:x = S.data[++S.top];
return true;
}

// 方式二(与后面的对应着的)
bool Push(SqStack &S, ElemType x) {
if (S.top == MaxSize) return false; // 判断是否栈满

S.top = S.top + 1;
S.data[S.top] = x;
// 上面两条语句可以合并为:x = S.data[++S.top];
return true;
}

方式一:

image-20240217165450907

方式二:

image-20240217170911051

出栈

1
2
3
4
5
6
7
8
bool Pop(SqStack &S, ElemType &x) {	
if (S.top == -1) return false; // 判断栈是否为空

x = S.data[S.top]; // x就是记录一下马上要弹出的栈顶元素
S.top = S.top - 1; // 栈底元素弹出S.top = S.top - 1
// 上面两条语句可以合并为:x = S.data[S.top--];
return true; // 出栈成功,而且仅仅是逻辑删除
}
image-20240217170152898

拓展: 共享栈(小小了解即可)

image-20240217171235473

说白了就是两个栈放到内存中同一块连续空间中存储,一个栈从底往上添加元素,另一个从顶往下添加元素。

下一节内容是:9、栈与队列——链栈!!!

一定要把本节内容看懂再往下看,不然会非常痛苦的哦o(╥﹏╥)oo(╥﹏╥)oo(╥﹏╥)o……..