栈和队列——栈-EW帮帮网

1. 栈的定义

栈是一种特殊的线性表，只允许在一端（栈顶）进行插入和删除操作。一个栈的两端分别叫做栈顶和栈底，他们有着不同的作用。我们把栈的插入操作叫做进栈（压栈、入栈），栈的删除操作叫做出栈（弹栈）

栈顶：允许插入和删除的一端。
栈底：最先入栈的元素放置在栈底。
栈的插入：进栈，也称压栈、入栈。
栈的删除：出栈，也称弹栈。

简单来说，栈就像一个杯子，只有一端开口，倒入和倒出都在有开口的一端，即任何操作都在栈顶。除此之外，栈的操作原则为 后进先出（Last In First Out），简称 LIFO 结构。

2. 栈的实现（顺序存储结构）

前面我们说栈是一种特殊的线性表，而线性表可分为顺序表和顺序表。那么在这里栈的实现可以使用顺序表，也可以使用链表。

顺序存储结构，也就是用数组来实现。在实现之前，我们要考虑一个问题，栈顶和栈底在数组的哪个位置比较好？在顺序表中，尾部的插入删除操作比较方便，所以我们就把下标为 0 的一端作为栈底，另一端作为栈顶。

2.1 栈的结构定义

typedef int STDataType;		//根据需要可随时更改类型
typedef struct Stack
{
	STDataType* a;	//数组名
	int top;		// 栈顶元素下标
	int capacity;  	// 容量 
}Stack;

2.2 栈的初始化

void StackInit(Stack* ps) {
	assert(ps);

	ps->a = NULL;
	ps->top = -1;		//这里top的初始位置定义为-1
	//ps->top = 0;		//也可以初始化为0（表示为栈顶元素的下一个位置），下面就要做相应的更改
	ps->capacity = 0;
}

2.3 栈的插入

void StackPush(Stack* ps, STDataType data) {
	assert(ps);

	if (ps->top + 1 == ps->capacity) {			//若ps->top初始化为0，这里ps->top就不用 +1
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;		//容量不够就开辟空间
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);		//为数组开辟空间
		if (tmp == NULL) {
			perror("realloc fail!");
			return;
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}

	++ps->top;				//top先++
	ps->a[ps->top] = data;	//插入数据

	/*ps->top初始化为0时*/
	//ps->a[ps->top] = data;
	//ps->top++;

}

图解：

2.4 栈的删除

void StackPop(Stack* ps) {
	assert(ps);
	assert(ps->top >= 0);		//若ps->top初始化为0，改为assert(ps->top > 0);

	ps->top--;
}

图解：

2.5 获取栈顶元素

直接返回 top 位置的数据。

STDataType StackTop(Stack* ps) {
	assert(ps);
	assert(ps->top >= 0);		//若ps->top初始化为0，改为assert(ps->top > 0);

	return ps->a[ps->top];		//若ps->top初始化为0，改为ps->a[ps->top-1]
}

2.6 获取栈中有效元素个数

int StackSize(Stack* ps) {
	assert(ps);

	return ps->top + 1;		//若ps->top初始化为0，则去掉 +1
}

2.7 判断栈是否为空

如果栈为空返回非零结果，如果不为空返回0

bool StackEmpty(Stack* ps) {
	assert(ps);

	return ps->top == -1;		//若ps->top初始化为0，则将 -1 改为 0 
}

2.8 栈的销毁

void StackDestroy(Stack* ps) {
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->top = -1;		//若ps->top初始化为0，则将 -1 改为 0 
	ps->capacity = 0;
}

2.9 功能综合（顺序栈）

这里的重点是 top 初始化的问题，不懂的要多琢磨一下哦。（建议自行使用接口方式实现）👊

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

//顺序栈
typedef int STDataType;		//根据需要可随时更改类型
typedef struct Stack
{
	STDataType* a;	//数组名
	int top;		// 栈顶元素下标
	int capacity;  	// 容量 
}Stack;

//栈的初始化
void StackInit(Stack* ps) {
	assert(ps);

	ps->a = NULL;
	ps->top = -1;		//这里top的初始位置定义为-1
	//ps->top = 0;		//也可以初始化为0（表示为栈顶元素的下一个位置），下面就要做相应的更改
	ps->capacity = 0;
}

//栈的插入
void StackPush(Stack* ps, STDataType data) {
	assert(ps);

	if (ps->top + 1 == ps->capacity) {			//若ps->top初始化为0，这里ps->top就不用 +1
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;		//容量不够就开辟空间
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);		//为数组开辟空间
		if (tmp == NULL) {
			perror("realloc fail!");
			return;
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}

	++ps->top;				//top先++
	ps->a[ps->top] = data;	//插入数据

	/*ps->top初始化为0时*/
	//ps->a[ps->top] = data;
	//ps->top++;
}

//栈的删除
void StackPop(Stack* ps) {
	assert(ps);
	assert(ps->top >= 0);		//若ps->top初始化为0，改为assert(ps->top > 0);

	ps->top--;
}

//获取栈顶元素
STDataType StackTop(Stack* ps) {
	assert(ps);
	assert(ps->top >= 0);		//若ps->top初始化为0，改为assert(ps->top > 0);

	return ps->a[ps->top];		//若ps->top初始化为0，改为ps->a[ps->top-1]
}

//获取栈中有效元素个数
int StackSize(Stack* ps) {
	assert(ps);

	return ps->top + 1;		//若ps->top初始化为0，则去掉 +1
}

//判断栈是否为空
bool StackEmpty(Stack* ps) {
	assert(ps);

	return ps->top == -1;		//若ps->top初始化为0，则将 -1 改为 0 
}

//栈的销毁
void StackDestroy(Stack* ps) {
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->top = -1;		//若ps->top初始化为0，则将 -1 改为 0 
	ps->capacity = 0;
}

int main(）{
	
	Stack ps;
	StackInit(&ps);
	StackPush(&ps, 1);
	StackPush(&ps, 2);
	StackPush(&ps, 3);
	StackPop(&ps);
	printf("Top:%d \n", StackTop(&ps));
	StackPush(&ps, 4);
	StackPush(&ps, 5);
	printf("size:%d\n",StackSize(&ps));


	while (!StackEmpty(&ps)) {
		printf("%d ", StackTop(&ps));
		StackPop(&ps);
	}
	printf("\n");
	return 0;
}

3. 栈的实现（链式存储结构）

同样，在实现之前，我们还是要考虑栈顶和栈底在哪个位置。说到链表我们会想到头结点，如果没有头结点，链表也会需要一个头指针。如果把栈顶位置和头指针放在一起，是不是就可以省去头结点呢？当然，我们会把栈顶指针 top 代替头指针。这样一来，栈顶就在链表的头部，栈底就在另一端。
由于栈只能对栈顶进行操作，而我们把头部当成栈顶，所以链栈的插入删除就好比 单链表的头插、头删。

在单链表 中我们以头指针方向作为栈顶，另一端作为栈底。
如果用双向链表 来实现，栈顶和栈底的位置任意（任意一端都可作为栈顶或栈底）。

这里我们就使用单链表来实现

3.1 栈的结构定义

typedef int SLDataType;			//可根据需求改变
typedef struct StackLinklist {
	SLDataType val;				//数据域
	struct StackLinklist* next;	//指针域
}StackLinklist;

typedef struct {
	StackLinklist* top;		//结构体指针
	int count;				//元素个数
}StackLL;

3.2 栈的初始化

void StackLInit(StackLL* psl) {
	assert(psl);

	psl->top = NULL;
	psl->count = 0;
}

3.3 栈的插入

栈的开口只有一端，所以插入只能在一端操作，就无需再写一个函数来创建新结点，直接在插入函数中实现即可。（如果还是想写一个创建结点的函数也没有问题😄）

void StackLPush(StackLL* psl, SLDataType x) {
	assert(psl);

	StackLinklist* newnode = (StackLinklist*)malloc(sizeof(StackLinklist));	//创建新结点
	if (newnode == NULL) {
		perror("malloc fail!");
		return;
	}
	newnode->next = NULL;
	newnode->val = x;		//数据域赋值

	newnode->next = psl->top;
	psl->top = newnode;
	psl->count++;		//元素个数 +1
}

图解：
链栈入栈

3.4 栈的删除

void StackLPop(StackLL* psl) {
	assert(psl);
	assert(psl->top);

	StackLinklist* pop = psl->top;	
	psl->top = pop->next;
	free(pop);
	pop = NULL;

	psl->count--;		//元素个数 -1
}

图解：
链栈出栈

3.5 获取栈顶元素

可以直接通过栈顶指针 top 访问结点获取数据。

SLDataType StackLTop(StackLL* psl) {
	assert(psl);
	assert(psl->top);

	return psl->top->val;
}

3.6 获取栈中有效数据个数

在结构体定义时，就包含了计算元素个数的成员 count ，一定要注意在栈的插入和删除部分不要忘了对 count 加减。

int StackLCount(StackLL* psl) {
	assert(psl);

	return psl->count;
}

3.7 判断栈是否为空

bool StackLEmpty(StackLL* psl) {
	assert(psl);

	return psl->top == NULL;
}

3.8 栈的销毁

void StackLDestroy(StackLL* psl) {
	assert(psl);

	StackLinklist* cur = psl->top;		//先保存栈顶的位置
	
	while (cur) {
		StackLinklist* Next= cur->next;	//保存栈顶下一个元素的位置
		free(cur);				//释放
		cur = Next;			//cur再指向Next
	}
	
	psl->top = NULL;	//置空
	psl->count = 0;		//归零
}

3.9 功能综合（链栈）

这里我们就通过接口分层来综合代码。

stack.h:

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

//链式栈
typedef int SLDataType;

typedef struct StackLinklist {
	SLDataType val;
	struct StackLinklist* next;
}StackLinklist;

typedef struct {
	StackLinklist* top;
	int count;
}StackLL;


//初始化栈
void StackLInit(StackLL* psl);
//栈的插入
void StackLPush(StackLL* psl,SLDataType x);
//栈的删除
void StackLPop(StackLL* psl);
//获取栈顶元素
SLDataType StackLTop(StackLL* psl);
//获取栈中有效与元素个数
int StackLCount(StackLL* psl);
//检测栈是否为空，为空返会true，否则返回false
bool StackLEmpty(StackLL* psl);
//栈的销毁
void StackLDestroy(StackLL* psl);

stack.c:

#include"stack.h"

//栈的初始化
void StackLInit(StackLL* psl) {
	assert(psl);

	psl->top = NULL;
	psl->count = 0;
}

//栈的插入（入栈）
void StackLPush(StackLL* psl, SLDataType x) {
	assert(psl);

	StackLinklist* newnode = (StackLinklist*)malloc(sizeof(StackLinklist));	//创建新结点
	if (newnode == NULL) {
		perror("malloc fail!");
		return;
	}
	newnode->next = NULL;
	newnode->val = x;		//数据域赋值

	newnode->next = psl->top;
	psl->top = newnode;
	psl->count++;		//元素个数 +1
}

//栈的删除（出栈）
void StackLPop(StackLL* psl) {
	assert(psl);
	assert(psl->top);

	StackLinklist* pop = psl->top;	
	psl->top = pop->next;
	free(pop);
	pop = NULL;

	psl->count--;		//元素个数 -1
}

//获取栈顶元素
SLDataType StackLTop(StackLL* psl) {
	assert(psl);
	assert(psl->top);

	return psl->top->val;
}

//获取栈中有效元素个数
int StackLCount(StackLL* psl) {
	assert(psl);

	return psl->count;
}

//检测栈是否为空，为空返回true，否则返回false
bool StackLEmpty(StackLL* psl) {
	assert(psl);

	return psl->top == NULL;
}

//栈的销毁
void StackLDestroy(StackLL* psl) {
	assert(psl);

	StackLinklist* cur = psl->top;		//先保存栈顶的位置
	
	while (cur) {
		StackLinklist* Next= cur->next;	//保存栈顶下一个元素的位置
		free(cur);				//释放
		cur = Next;			//cur再指向Next
	}
	
	psl->top = NULL;	//置空
	psl->count = 0;		//归零
}

test.c:

int main(){

	StackLL psl;
	StackLInit(&psl);
	StackLPush(&psl, 1);
	StackLPush(&psl, 2);
	StackLPush(&psl, 3);
	printf("%d \n", StackLTop(&psl));
	
	StackLPop(&psl);

	printf("size:%d \n", StackLCount(&psl));
	StackLPush(&psl, 4);
	StackLPush(&psl, 5);

	while (!StackLEmpty(&psl)) {
		printf("%d ", StackLTop(&psl));
		StackLPop(&psl);
	}

	StackLDestroy(&psl);
	return 0;
}

4.顺序栈和链栈的选择

名称	顺序栈	链栈
存储方式	连续	不连续
空间利用率	高	低
访问方式	连续访问	随机访问
容量	可自动扩容	可自动扩容

在容量上，虽然两者都能够自动扩容，但顺序栈会有空间浪费的情况，而链栈就不存在浪费的情况。顺序栈和链栈各有优缺点，要根据实际情况来选择合适的结构。

如果以上的内容都没问题，那么可以试试实现两个栈共享空间的情况，两栈共享空间主要是注意共享栈空间满时改如何判断。相信这对你也不成问题。😄

栈和队列——栈