栈的概念

栈的定义

• **栈(stack)**是限定仅在表尾进行插入和删除操作的线性表。

• 我们把允许插入和删除的一端称为栈顶（top),另一端称为栈底（bottom)，不含任何数据元素的栈称为空栈。

• 栈又称为后进先出(Last In First Out)的线性表，简称LIFO结构。

为什么在表尾进行各种操作？
因为表尾的插入操作以及删除操作时间复杂度都为O（1）。

特点

• 栈是一个线性表，即栈元素有前驱后继关系。定义是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶，而不是栈底。
• 栈底是固定的，最先进栈的只能在栈底。

例子

为了更好理解栈，可以这样想象
例如：
子弹弹夹：最先装进去的子弹就在最底部，最后装进去的子弹先打出去。
厨房中一叠叠的餐盘：餐盘一个个叠起来后，最先用的是最上面的，即最后一个叠上去的；最后用的是第一个盘子。。。

顺序栈结构体定义

typedef int ElemType;
#define INIT_SIZE 10

//顺序栈的定义
typedef struct Stack
{
	ElemType *base;// 1
	int top;// 2
	int stacksize;//  3
}Stack, *PStack;

1. 数据域 用来保存malloc申请的空间
2. 栈顶指针，（1.其中有效数据的个数）（2.用来表示下一个插入位置的下标）
3. 用来保存当前stack总共有多少空间（扩容就在这）。

stack.h

#pragma once

typedef int ElemType;
#define INIT_SIZE 10

//顺序栈的定义
typedef struct Stack
{
	ElemType *base;//数据域 用来保存malloc申请的空间
	int top;//栈顶指针，（1.其中有效数据的个数）（2.用来表示下一个插入位置的下标）
	int stacksize;//用来保存当前stack总共有多少空间（扩容就在这）
}Stack, *PStack;

//顺序栈的操作有哪些？
//增删改查 

//初始化
void Init_stack(PStack ps);

//入栈（或者叫压栈 push）
bool Push(PStack ps, ElemType val);

//出栈（或者叫弹栈 pop（获取顶部数据，并且删除））//rtval是一个输出参数（C语言讲到）
bool Pop(PStack ps, ElemType* rtval);

//获取顶部元素值 top（获取顶部数据）
bool Top(PStack ps, ElemType* rtval);

//获取其有效数据个数
int Get_length(PStack ps);

//判空
bool IsEmpty(PStack ps);

//判满
bool IsFull(PStack ps);

//扩容
static void Inc(PStack ps);

//清空   一间房住了一户人  清空相当于把人赶出去
void Clear(PStack ps);

//销毁  一间房住了一户人  销毁相当于把人赶出去还把房烧了
void Destroy(PStack ps);

//打印
void Show(PStack ps);

初始化

//初始化
void Init_stack(PStack ps)
{
	//1.判空
	assert(ps != nullptr);
	if(nullptr == ps)
	{
		return;
	}

	//2.将成员初始化
	ps->base = (ElemType*)malloc(sizeof(ElemType) * INIT_SIZE);
	ps->stacksize = INIT_SIZE;
	ps->top = 0;
}

为什么断言之后还要再if判断？
因为我们编写程序时用的版本为debug版本，而到了用户手中的是release版本，是看不到assert()断言这一步的。

入栈

栈的插入操作，也叫进栈，压栈。

//入栈（或者叫压栈 push）
bool Push(PStack ps, ElemType val)
{
	//1.
	assert(ps != nullptr);

	//2.判断栈满了没
	if(IsFull(ps))
	{
		Inc(ps);//3.如果满了 则扩容
	}
	//4.如果没满或者扩容完毕  则插入
	/*ps->base[ps->top] = val;
	ps->top++;*/
	ps->base[ps->top++] = val;

	return true;
}

图示

出栈

栈的删除操作，也叫弹栈。

//出栈（或者叫弹栈 pop（获取顶部数据，并且删除））
//rtval是一个输出参数
bool Pop(PStack ps, ElemType* rtval)
{
	//1.assert
	assert(ps != nullptr);
	//2.判断栈是否为空
	if(IsEmpty(ps))
	{
		return false;
	}
	//3.出栈
	/**rtval = ps->base[ps->top-1];
	ps->top--;*/
	*rtval = ps->base[--ps->top];

	return true;
}

图示

扩容

static void Inc(PStack ps)
{
	//不需要断言
	ps->base = (ElemType*)realloc(ps->base, sizeof(ElemType) * ps->stacksize * 2);
	assert(ps->base != nullptr);

	ps->stacksize *= 2;
}

清空和销毁

//清空  
void Clear(PStack ps)
{
	ps->top = 0;
}

//销毁  
void Destroy(PStack ps)
{
	ps->top = 0;
	free(ps->base);
	ps->base = nullptr;
}

清空： 一间房住了一户人 清空相当于把人赶出去。
销毁：一间房住了一户人 销毁相当于把人赶出去还把房烧了。

只读接口

//获取顶部元素值 top（获取顶部数据）
bool Top(PStack ps, ElemType* rtval)
{
	//1.assert
	assert(ps != nullptr);
	//2.判断栈是否为空
	if(IsEmpty(ps))
	{
		return false;
	}
	//3.获取其顶部数据
	*rtval = ps->base[ps->top-1];

	return true;
}

//获取其有效数据个数
int Get_length(PStack ps)
{
	assert(ps != nullptr);
	return ps->top;
}

//判空
bool IsEmpty(PStack ps)
{
	return ps->top == 0;
}

//判满
bool IsFull(PStack ps)
{
	return ps->top == ps->stacksize;
}

//打印
void Show(PStack ps)
{
	assert(ps != nullptr);
	for(int i=0; i<ps->top; i++)
	{
		printf("%d ", ps->base[i]);
	}
	printf("\n");
}

链栈定义

图示

栈顶在链表的头部。

对于链栈来说，基本不存在栈满的情况，除非是内存已经没有可使用的空间了。

结构体定义

typedef int ElemType;
typedef struct StackNode
{
	ElemType data;//数据域
	StackNode* next;//指针域
}StackNode, * PStackNode;

typedef struct LinkStack
{
	struct SackNode* top;
	int count;
}LinkStack, * PLinkStack;

初始化

//初始化
void Init_stack(PLinkStack ps)
{
	assert(ps != nullptr);

	ps->count = 0;
}

入栈

图示

函数实现

//入栈（或者叫压栈 push） 头插
bool Push(PLinkStack ps, ElemType val)
{
	assert(ps != nullptr);

	StackNode* pnewnode = (StackNode*)malloc(sizeof(StackNode) * 1);
	assert(pnewnode != nullptr);
	pnewnode->data = val;
	
	pnewnode->next = ps->top;
	ps->top = pnewnode;
	ps->count++;

	return true;
}

出栈

图示

函数实现

//出栈 尾删（或者叫弹栈 pop（获取顶部数据，并且删除））
bool Pop(PLinkStack ps, ElemType* rtval)
{
	assert(ps != nullptr);
	if (IsEmpty(ps))
	{
		return false;
	}

	StackNode* p = ps->top;
	*rtval = p->data;
	ps->top = p->next;

	free(p);
	p = nullptr;
	ps->count--;

	return true;
}

清空和销毁

//清空   
void Clear(PLinkStack ps)
{
	Destroy(ps);
}

//销毁  
void Destroy(PLinkStack ps, ElemType* rtval)
{
	assert(ps != nullptr);

	while (!IsEmpty(ps))
	{
		Pop(ps, rtval);
	}
}

只读接口

//获取顶部元素值 top（获取顶部数据）
bool Top(PLinkStack ps, ElemType* rtval)
{
	assert(ps != nullptr);
	if (IsEmpty(ps))
	{
		return false;
	}

	*rtval = ps->top->data;

	return true;
}

//获取其有效数据个数
int Get_length(PLinkStack ps)
{
	assert(ps != nullptr);

	return ps->count;
}

//判空
bool IsEmpty(PLinkStack ps)
{
	return ps->count == 0;
}

//打印
void Show(PLinkStack ps)
{
	assert(ps != nullptr);

	StackNode* p = ps->top;

	for (p; p->next != nullptr; p = p->next)
	{
		printf("%d ", p->data);
	}
	printf("\n");
}

总结

顺序栈和链式栈它们的入栈出栈操作都很简单，时间复杂度都为O(1)。
对于空间性能，顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题，但它的优势是存取时定位很方便，而链栈则要求每个元素都有指针域，这同时也增加了一些内存开销，但对于栈的长度无限制。

所以，如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。