【C】初阶数据结构5 -- 栈

  前面学习了两种最基本的数据结构 -- 顺序表和链表，接下来就可以基于这两种数据结构来实现其他数据结构了。其实，其他的数据结构的物理结构要么是数组，要么就是链表，所以学好顺序表和链表是学好其他数据结构的基础。接下里，我们就来看一个新的数据结构 -- 栈。

---

目录

1  栈的概念与特点

2  栈的结构 

1） 逻辑结构

2） 物理结构 

 3  栈的基本操作的实现

1） 初始化和销毁

2） 入栈与出栈、

（1） 入栈

（2） 出栈

3）  取栈顶元素、判空、获取有效元素个数

4  代码

---

重点一  栈的特点

1  栈的概念与特点

  栈：一种特殊的线性表，其只允许在一端进行插入和删除数据。插入和删除数据的一端叫做栈顶，另一端叫做栈底。

  入栈（压栈）：往栈中插入数据的操作叫做入栈。

  出栈：栈中删除数据的操作叫做出栈。

  特点：栈中的数据遵循LIFO原则(last in first out)，也就是后进先出原则。

  栈的特点特别重要，一般使用栈都是因为其后进先出的特点，下面来做一个题来理解一下其后进先出的特点：

假设有一个栈，数据入栈的先后顺序为 a b c d e ，请在以下选项中选出错误的出栈顺序（）A. a b c d e                    B. c b d a eC. d b c a e                    D. e d c b a

 该题的正确答案为 C，因为如果 d 先出栈的话，说明 a，b，c 均以入栈，如何要接着出栈的话，应是 c 先出栈，而不是 b 先出栈。

  需要注意的一点就是，出栈顺序并不是等数据全部入栈之后才能出栈。比如 A 选项，就是入栈一个数据，然后出栈一个数据。

---

重点二  栈的结构

2  栈的结构 

1） 逻辑结构

  我们可以把栈想象成以下的一个结构：

2） 物理结构 

  栈的物理结构既可以选择用链式结构来实现，也可以选择用数组，也就是顺序表来实现。这里选择使用数组来实现，因为栈后进先出的特性，规定了其只能在尾部进行插入和删除数据，而对于顺序表来说，在尾部插入和删除数据又十分方便，所以这里选择使用顺序表来实现栈。

  既然是使用顺序表来实现栈，所以栈的结构和顺序表十分相似，只不过就是把 size 变为了 top，用来表示栈的顶部元素的位置：

//将int定义为栈里面的数据类型
typedef int STDataType;
//栈的结构
typedef struct Stack
{STDataType* arr;//栈中的存放数据的数组int capacity;//栈的容量大小int top;//栈顶
}ST;

---

重点三  实现栈

 3  栈的基本操作的实现

  对于一个栈来说，其主要操作只有入栈、出栈、取栈顶元素、初始化、销毁、判空、获取有效元素个数。

1） 初始化和销毁

    栈的初始化和销毁与顺序表可以说是一模一样，这里就不做多余讲解，可以去回顾一下顺序表（也可以看下面代码理解一下）。

---

2） 入栈与出栈、

（1） 入栈

  入栈的操作就相当于顺序表中的尾差，其基本过程如图所示：

可以看到，就是顺序表的尾插操作，只不过就是把 size 变成了 capacity 而已。

（2） 出栈

  出栈就是顺序表的尾删，所以只需要让 --top 就可以了。

---

3）  取栈顶元素、判空、获取有效元素个数

  这3个操作的实现都很简单。取栈顶元素就是返回 arr 数组中 top - 1 下标的数据，但要注意栈要非空，才能返回栈顶元素，所以要先对栈是否为空断言；判空就是判断 top 是否等于0；获取有效元素个数就是返回 top 。

---

4  代码

Stack.h文件：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int STDataType;
typedef struct Stack
{STDataType* arr;int capacity;int top;
}ST;//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//取栈顶元素
STDataType STTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//栈是否为空
bool STEmpty(ST* ps);

Stack.c文件：

#include"Stack.h"//初始化
void STInit(ST* ps)
{assert(ps);ps->arr = NULL;ps->capacity = ps->top = 0;
}//销毁
void STDestroy(ST* ps)
{assert(ps);free(ps->arr);ps->arr = NULL;ps->capacity = ps->top = 0;
}//入栈
void STPush(ST* ps, STDataType x)
{//相当于顺序表的尾插assert(ps);//如果数组满了。需要增容if (ps->capacity == ps->top){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, sizeof(STDataType) * newCapacity);if (tmp == NULL){perror("realloc fail！\n");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//不要忘记让top++ps->arr[ps->top++] = x;
}
//栈是否为空
bool STEmpty(ST* ps)
{assert(ps);//判断top是否为0就可以了return ps->top == 0;
}
//出栈
void STPop(ST* ps)
{//相当于顺序表的尾删assert(!STEmpty(ps));--ps->top;
}//取栈顶元素
STDataType STTop(ST* ps)
{assert(ps);//栈不能为空assert(!STEmpty(ps));//只取栈顶元素，不删除数据int pos = ps->top - 1;return ps->arr[pos];
}//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}

test.c文件：

#include"Stack.h"
void Test4()
{ST st;STInit(&st);//测试入栈STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);for (int i = 0; i < st.top; i++){printf("%d ", st.arr[i]);}printf("\n");//测试出栈与取栈顶元素STPop(&st);STPop(&st);STPop(&st);STPop(&st);//STPop(&st);/*int ret = STTop(&st);printf("%d ", ret);printf("\n");for (int i = 0; i < st.top; i++){printf("%d ", st.arr[i]);}printf("\n");*/bool ret1 = STEmpty(&st);if (ret1){printf("栈为空！\n");}else{printf("栈不为空！\n");}int ret = STSize(&st);printf("%d ", ret);STDestroy(&st);
}
int main()
{Test4();return 0;
}

---

   可以看到实现栈，其实就是实现顺序表的部分接口，学好顺序表和链表是实现其他数据结构的基础。所以一定要把基础学扎实，才能越学越好。