数据结构 - 栈

一、什么是栈(Stack)

1）栈的基本概念

1）栈(Stack) 是只允许在一端进行插入或者删除的操作的线性表
2）线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，其中n为表长，当n=0时线性表是空表。一般表示为：

2）栈的图示

二、栈的基本操作

InitStack(&S)：初始化栈。构造一个空栈 S，分配内存空间。

DestroyStack(&S)：销毁栈。销毁并释放栈 S 所占用的内存空间。

Push(&S,x)：进栈，若栈S未满，则将x加入使之成为新栈顶。

Pop(&S,&x)：出栈，若栈S非空，则弹出栈顶元素，并用x返回。

GetTop(S, &x)：读栈顶元素。若栈 S 非空，则用 x 返回栈顶元素

其他常用操作：
StackEmpty(S)：判断一个栈 S 是否为空。若S为空，则返回true，否则返回false。

三、代码实现

1）栈的初始化

#include 
#define MaxSize 10
typedef int etype;
typedef struct {
    etype data[MaxSize];
    int top;
}SqStack;
//栈的初始化
bool InitStack(SqStack &S){
    S.top = -1;   //栈的一个指针，用来表示下标
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12

2）进栈

//进栈
bool Push(SqStack &S,etype e){
    if(MaxSize-1 == S.top)  //考虑栈堆满了的情况
        return false;
    S.top++;               //下标
    S.data[S.top] = e;     //插入元素
    printf("进栈的是：%c\n",S.data[S.top]);
    return true;
}
1
2
3
4
5
6
7
8
9

3）出栈

//出栈
bool Pop(SqStack &S,etype &e){
    if(-1 == S.top)       //栈为空
        return false;
    e = S.data[S.top];
    printf("出栈的是：%c\n",S.data[S.top]);
    S.top--;
    return true;
}
1
2
3
4
5
6
7
8
9

4）实例：进制转换

输入一个十进制的数，转化为二进制

void conversion(){
    SqStack S;
    InitStack(S);

    int N;
    scanf("%d",N);
    while(N){
        Push(S,N%2);
        N = N / 2;
    }
    int e;

    while (S.top != -1){
        Pop(S,e);
        printf("%d",e);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

四、知识点