手撕数据结构 —— 栈（C语言讲解）

1.认识栈

什么是栈

栈的示意图

2.如何实现栈

3.栈的实现

Stack.h中接口总览

具体实现

结构的定义

初始化栈

销毁栈

入栈

出栈

取栈顶元素

获取有效元素的个数

判断栈是否为空

4.完整代码附录

Stack.h

Stack.c

1.认识栈

什么是栈

栈是一种特殊的线性表，只允许在固定的一端进行数据的插入和删除操作；

进行数据的插入和删除的一端叫做栈顶，另一端叫做栈底。
栈中的数据必须严格遵守后进先出的原则，这也是栈这种数据结构最重要的特点。

栈的示意图

两个专业术语：

入栈：栈的插入数据元素的操作叫做入栈。

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

入栈和出栈都是在栈顶进行的。

2.如何实现栈

要想实现栈，必须满足以下两个条件：

a、控制在一端进行数据的插入和删除
b、满足后进先出的原则。

基于上述条件，我们可以使用数组或者链表来实现栈，那么使用哪种数据结构来实现栈更好呢？

我们可以对比一下：

	数组（顺序表）	链表（单链表）
头插效率	O(N)	O(1)
头删效率	O(N)	O(1)
尾插效率	O(1)	O(N)
尾删效率	O(1)	O(N)

可以看出，使用数组（顺序表）来实现栈的话，需要将尾部作为栈顶，插入数据和删除数据的时间复杂度都是O(1)。使用链表（单链表）来实现栈的话，需要将头部作为栈顶，插入数据和删除数据的时间复杂度都是O(1)。

但是相对而言，使用数组实现栈更优，因为数组没有太多的指针操作，删除数据的时候只需要让size-- 即可（size是数组中有效元素的个数），插入数据的时候直接赋值即可。

我们实现栈的时候，采用数组的形式实现数组栈。

3.栈的实现

实现栈的时候，我们主要实现Stack.h 和 Stack.c这两个文件，Stack.h用来存放声明，Stack.c用来存放定义。

Stack.h中接口总览

具体实现

结构的定义

因为静态的栈不实用，我们实现的数组栈采用动态增长的形式。

a指向动态开辟的内存空间的起始地址。
top指向栈顶元素的下一个位置。
capacity表示栈的容量，当容量不够的时候，需要动态扩容。

初始化栈

初始化栈的之后，将a置为空，capacity和top都为0。

top初始化为0表示top指向栈顶元素的下一个位置。
top如果初始化为-1表示top指向栈顶元素。
两种方式实现都可以，我们采用第一种，这样的好处是top的值直接就可以表示栈中数据元素的个数。

注意：指向物理空间的指针ps不能为空，后面涉及该指针变量的地方都一样。

销毁栈

销毁栈的时候，只需要将动态申请的空间释放，并将指向这块空间的指针置空；然后将top和capacity都置为0即可。

入栈

实现入栈需要注意以下几个点：

栈空间不能为空，使用断言assert()暴力判断。
注意空间是否足够，空间不够时需要扩容。
元素入栈之后，top记得++。

出栈

出栈时需要注意以下几点：

指向物理空间的指针不能为空。
栈中元素个数 >0 时元素才能出栈。
元素出栈之后记得将top-- 。

取栈顶元素

我们定义结构的时候，将top定义为栈顶元素的下一个位置，top-1就表示栈顶元素的下标，直接返回栈顶元素即可。

获取有效元素的个数

top也能表示栈中有效元素的个数，直接返回top即可。

判断栈是否为空

top表示栈中有效数据的个数，当top == 0时，栈为空；当top != 0时，栈不为空。

4.完整代码附录

Stack.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;    // 指向动态开辟的顺序表 
	int top;          // 指向栈顶元素的下一个位置 
	int capacity;     // 表示栈的容量 
}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->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void STDestroy(ST* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

void STPush(ST* ps, STDataType x)
{
	assert(ps);

	if (ps->top == ps->capacity)     // 当 top==capacity时就需要扩容了  
	{
		// 初始空间为4，扩容按照两倍扩 
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		
		// 当a为空的时候，realloc的功能类似于malloc 
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		
		if (tmp == NULL)             // 判断扩容是否成功 
		{
			perror("realloc fail");
			exit(-1);
		}

		ps->a = tmp;                 // 将开辟的空间赋值给变量a 
		ps->capacity = newCapacity;  // 更新容量 
	}

	ps->a[ps->top] = x;              // 元素入栈 
	ps->top++;                       // top++指向栈顶元素的下一个位置 
}


void STPop(ST* ps)
{
	assert(ps);          // 指针不能为空 

	assert(ps->top > 0); // 栈中元素个数 >0 元素才能出栈 

	--ps->top;           // 元素出栈之后记得将top-- 
}

STDataType STTop(ST* ps)
{
	assert(ps);            
 
	assert(ps->top > 0);        // 栈中有元素 

	return ps->a[ps->top - 1];  // 返回栈顶元素 
}

int STSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

bool STEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}