【数据结构】栈的基本原理与实现

阅读本文，需要对C语言的知识有所掌握，参考我的C语言合集。

C语言合集

1. 栈的定义

stack:堆栈，又称栈或堆叠，先进后出-FILO(First In Last Out)。

栈：只允许在一端进行插入或删除操作的线性表。

重要术语：栈顶、栈底、空栈。

2. 栈的顺序存储实现

顺序存储实现栈

typedef struct{
    Elemtype data[8];
    int top;
}SqStack;
SqStack S;

初始化栈（空栈）

# 表示栈为空，可以作为初始化栈
S.top=-1

元素入栈

S.data[++S.top]=4

# 相当于以下两行
S.top=S.top+1;
S.data[S.top]=4;

元素出栈

x=S.data[S.top--];

# 相当于以下两行，x表示出栈的元素值
x=S.data[S.top];
S.top=S.top-1;

栈满

# 表示栈满
S.top=MaxSize-1;

3. 共享栈

两个栈共享同一片空间，两个栈从两边往中间增长。

#define MaxSize 8  // 定义栈中元素的最大个数
typedef struct{
    ElemType data[MaxSize];  // 静态数组存放栈中元素
    int top0;   // 0号栈栈顶指针
    int top1;   // 1号栈栈顶指针
}ShStack;

初始化栈

void InitStack(ShStack &S){
    S.top0=-1;   // 初始化栈顶元素
    S.top1=MaxSize;
}

栈满

top0 + 1==top1

4. 栈的链式存储实现

链式存储实现栈

typedef struct Linknode{
    ElemType data;   // 数据域
    struct Linknode *next;  // 指针域
}*LiStack;  // 栈类型定义

初始化栈（空栈）

# 空栈，也可以初始化栈
LiStack Lhead=(LiStack)malloc(sizeof(struct Linknode));
Lhead->next=NULL;
LiStack top=NULL;

元素入栈

top=(LiStack)malloc(sizeof(struct Linknode));
top->next=NULL;
top->data=1;
top->next=Lhead->next;
Lhead->next=top;

元素出栈

# c为要出栈的元素。链表表示栈，相当于头插法，那么出栈就表示为
c=top->data;
Lhead->next=top->next;
free(top);
top=Lhead->next;

栈空

# 为真，则栈为空
Lhead->next==null

注意：对于链表实现的栈，只要还有剩余内存，就可以继续添加元素，所以不做栈满判断的操作。

5. 实战操作

我们使用顺序存储的实现方式。

#include <stdio.h>

#define MaxSize 5
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize];  // 数组
    int top;
}SqStack;

// 初始化栈
void InitStack(SqStack &S){
    S.top=-1; // -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;
    return true;
}
// 出栈
bool Pop(SqStack &S,ElemType x){
    if(-1==S.top){
        return false;
    }
    x=S.data[S.top--];
    return true;
}

// 获取栈顶元素
bool GetTop(SqStack S,ElemType &x){
    if(-1==S.top){
        return false;
    }
    x=S.data[S.top];
    return true;
}
int main() {
    SqStack S;
    InitStack(S); // 初始化栈
    bool flag;
    flag=StackEmpty(S);// 判断栈是否为空
    if(flag){
        printf("stack is empty\n");
    }
    Push(S,3);  // 入栈
    Push(S,4);
    Push(S,5);
    Push(S,6);
    Push(S,7);
    Push(S,8); // 只能放5个元素，8实际没有放入
    ElemType m;
    flag=GetTop(S,m);// 获取栈顶元素
    if(flag){
        printf("top is %d\n",m);
    }
    flag=Pop(S,m); // 出栈
    if(flag){
        printf("pop is %d\n",m);
    }
    flag=GetTop(S,m);// 获取栈顶元素
    if(flag){
        printf("top is %d\n",m);
    }
    return 0;
}

F:\Computer\Project\practice\13\13.2-stack\cmake-build-debug\13_2_stack.exe
stack is empty
top is 7
pop is 7
top is 6

进程已结束，退出代码为 0

6. 小结

说明：顺序栈没有malloc内存空间，在函数执行结束后自动回收空间。