廖家龙的博客网站
栈的顺序存储实现
廖家龙 用心听，不照做
  2019-03-15 23:44:00   2024-07-18 23:44:56    463 字  2 分钟

顺序栈的缺点：栈的大小不可变

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
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>

#define MaxSize 10  //定义栈中元素的最大个数

//顺序栈的定义
typedef struct{
    int data[MaxSize];  //静态数组存放栈中元素
    int top;  //栈顶指针，top指向当前栈顶元素
}SqStack;  //Sq：sequence，顺序

//初始化栈
void InitStack(SqStack *S){
    S->top=-1;  //初始化栈顶指针
}

//判断栈空
bool StackEmpty(SqStack *S){
    if(S->top == -1){
        return true;  //栈空
    }
    else{
        return false;  //不空
    }
}

//进栈操作
bool Push(SqStack *S,int x){
    if(S->top==MaxSize-1){
        return false;  //栈满，报错
    }
    S->top=S->top+1;  //指针先+1
    S->data[S->top]=x;  //新元素入栈
    
    return true;
}

//出栈操作,并用x返回
bool Pop(SqStack *S,int *x){
    if(S->top==-1){
        return false;  //栈空，报错
    }
    (*x)=S->data[S->top];  //栈顶元素先出栈
    S->top=S->top-1;  //指针再-1，数据还残留在内存中，只是逻辑上被删除了
    return true;
}

//读栈顶元素操作
bool GetTop(SqStack *S,int *x){
    if(S->top==-1){
        return false;  //栈空，报错
    }
    (*x)=S->data[S->top];  //x记录栈顶元素
    return true;
}

int main(){
    SqStack S;  //声明一个顺序栈(分配空间)
    InitStack(&S);
    
    //...后续操作
}

共享栈：

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
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>

#define MaxSize 10  //定义栈中元素的最大个数

//共享栈：两个栈共享同一片空间
typedef struct{
    int data[MaxSize];  //静态数组存放栈中元素
    int top0;  //0号栈顶指针
    int top1;  //1号栈顶指针
}ShStack;

//初始化栈
void InitStack(ShStack *S){
    S->top0=-1;  //初始化栈顶指针
    S->top1=MaxSize;
}

//栈满条件：top0+1==top1

int main(){
    ShStack S;  //声明一个顺序栈(分配空间)
    InitStack(&S);
    
    //...后续操作
}