数据结构——栈

一.前言

栈和队列是两种重要的线性结构。从数据结构角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，它们是操作受限的线性表，因此，可称为限定性的数据结构。但从数据类型角度看，它们是和线性表不相同的两类重要的抽象数据类型。今天就来学习一下栈吧。

二.正文 

(1)定义

一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

最显著的特点：

后进先出（LIFO）:栈遵循“后进先出”原则，最后入栈的元素最先被弹出，类似于叠放的盘子。

有限访问性：只能访问栈顶元素，其他元素需依次弹出栈顶后才能访问，确保操作有序性。

再来认识两个概念。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。如下图：

栈的实现通常采用数组或链表两种方式。相较而言，数组实现更具优势，因为它在尾部插入数据的操作效率更高。

 (2)顺序栈的实现

数组实现具有一定优势，所以让我们先来看看顺序栈的实现

先来看看如何定义顺序栈吧

//静态栈
#define N 10
struct Stack
{
	int a[N];
	int top;
}ST;

这个是静态的，只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。 所以我们应该使用动态的。 

//动态栈
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

看着两个是不是很眼熟，跟我们之前学的顺序表很像 ，其实有些操作也差差不多，所以看看要实现什么功能吧。文件建立的准备工作跟之前一样就不解释了。

放在Stack.h中

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
//静态栈
//#define N 10
//struct Stack
//{
//	int a[N];
//	int top;
//}ST;

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);
//有效数据个数
int STSize(ST* ps);
//判空
bool STEmpty(ST* ps);
//返回栈顶元素
STDataType STTop(ST* ps);

2.1顺序栈的初始化

//初始化
void STInit(ST* ps)
{
	assert(ps);
	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps->top = 0;//top是栈顶元素的下一个位置
	//ps->top = -1;  //top是栈顶元素的位置
	ps->capacity = 4;
}

top取0或者-1都可以。top=0时top是栈顶元素的下一个位置；top = -1时top是栈顶元素的位置 。不同初始化方式会导致后续代码写法存在差异，只需选择其中一种实现方式即可，但需要明确理解这两种情况的含义。

2.2顺序栈的销毁

//销毁
void STDestroy(ST* ps)
{
	assert(ps);

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

2.3顺序栈的检查和扩容

因为任何插入都可能会面是否满的问题，所以我们要进行检查，若满了就扩容。

//顺序栈的检查和扩容
void STCheck(ST* ps)
{
	assert(ps);

	if (ps->top == ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		ps->a = tmp;
		ps->capacity *= 2;
	}
}

看来上面三个功能的编写大家是否发现跟顺序表是不是特别像。 

2.4顺序栈的入栈

如图所示：

代码如下: 

//插入
void STPush(ST* ps, STDataType x)
{
	assert(ps);
	STCheck(ps);

	ps->a[ps->top] = x;
	ps->top++;
}

2.4顺序栈的判空

顺序栈删除首先得知道栈为不为空，为空就没必要删除了。

我们初始化时0，所以判空时就判断它是否等于0即可。

//判空
bool STEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}

2.5顺序栈的删除 

//删除
void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	ps->top--;
}

2.6返回顺序栈的栈顶元素

因为top=0时top是栈顶元素的下一个位置，所以取值时要-1.

//返回栈顶元素
STDataType STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	return ps->a[ps->top - 1];
}

 2.7返回顺序栈的元素个数

//有效数据个数
int STSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

让我们来看看能否运行吧：

2.8完整代码 

#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"

//初始化
void STInit(ST* ps)
{
	assert(ps);
	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps->top = 0;//top是栈顶元素的下一个位置
	//ps->top = -1;  //top是栈顶元素的位置
	ps->capacity = 4;
}

//销毁
void STDestroy(ST* ps)
{
	assert(ps);

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

//顺序栈的检查和扩容
void STCheck(ST* ps)
{
	assert(ps);

	if (ps->top == ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		ps->a = tmp;
		ps->capacity *= 2;
	}
}

//插入
void STPush(ST* ps, STDataType x)
{
	assert(ps);
	STCheck(ps);

	ps->a[ps->top] = x;
	ps->top++;
}

//判空
bool STEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}

//删除
void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	ps->top--;
}

//返回栈顶元素
STDataType STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	return ps->a[ps->top - 1];
}

//有效数据个数
int STSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

(3)链表栈的实现

先来看看如何定义的，图片如下：

代码如下：

typedef struct Stack
{
	STDataType data;
	struct Stack* next;
}ST;

跟单链表的结构类似,来看看要满足什么功能吧

Stack中为了看起来形式一样，所以博主就都用双指针了

#pragma once

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

typedef int STDataType;
typedef struct Stack
{
	STDataType data;
	struct Stack* next;
}ST;

//销毁
void STDestroy(ST** ps);
//插入
void STPush(ST** ps, STDataType x);
//删除
void STPop(ST** ps);
//有效数据个数
int STSize(ST** ps);
//判空
bool STEmpty(ST** ps);
//返回栈顶元素
STDataType STTop(ST** ps);

3.1链栈的入栈

使用头插法，和顺序栈不同的是，链栈入栈前要判断是否满

//入栈
void STPush(ST** ps, STDataType x)
{
	ST* p = (ST*)malloc(sizeof(ST));
	if (p == NULL)
	{
		perror("malloc fail");
		return;
	}
	p->data = x;
	p->next = *ps;
	*ps = p;
}

3.2链栈的判空

如果等于空就返回1，不等则0

//判空
bool STEmpty(ST** ps)
{
	return *ps == NULL;
}

3.3链栈的出栈

和顺序栈同，需要判断是否为空，不同的是链栈需要释放出栈元素的栈顶空间

//出栈
void STPop(ST** ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	ST* p = *ps;
	*ps = (*ps)->next;
	free(p);
	p = NULL;
}

3.4链栈的取栈顶元素

不为空直接返回栈顶链表的data

//取栈顶元素
STDataType STTop(ST** ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	return (*ps)->data;
}

3.5链栈的有效数据个数

将cur=ps，然后不为空就+1

//有效数据个数
int STSize(ST** ps)
{
	int size = 0;
	ST* cur = *ps;
	while (cur != NULL)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

3.6链栈的销毁

//销毁
void STDestroy(ST** ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	ST* p=NULL;
	while(*ps!=NULL)
	{
		p = *ps;
		*ps = (*ps)->next;
		free(p);
		p = NULL;
	}
	*ps = NULL;
}

看看运行结果：

来看看完整代码：

#include "Stack.h"

//入栈
void STPush(ST** ps, STDataType x)
{
	ST* p = (ST*)malloc(sizeof(ST));
	if (p == NULL)
	{
		perror("malloc fail");
		return;
	}
	p->data = x;
	p->next = *ps;
	*ps = p;
}

//判空
bool STEmpty(ST** ps)
{
	return *ps == NULL;
}

//出栈
void STPop(ST** ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	ST* p = *ps;
	*ps = (*ps)->next;
	free(p);
	p = NULL;
}

//取栈顶元素
STDataType STTop(ST** ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	return (*ps)->data;
}

//有效数据个数
int STSize(ST** ps)
{
	int size = 0;
	ST* cur = *ps;
	while (cur != NULL)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

//销毁
void STDestroy(ST** ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	ST* p=NULL;
	while(*ps!=NULL)
	{
		p = *ps;
		*ps = (*ps)->next;
		free(p);
		p = NULL;
	}
	*ps = NULL;
}

 我们能发现顺序栈与顺序表类似，链栈和单链表类似，所以前面的知识我们要好好掌握。

(4)经典栈的题目

让我们来写一道关于栈的经典

有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。链接：20. 有效的括号 - 力扣（LeetCode）

思路：我们能知道用栈来可以达到题目要求，依次遍历字符串s，当是左括号时入栈，右括号是出栈一个进行匹配，若匹配则为正确，不匹配则是错的。来看看oj的代码吧。

bool isValid(char* s) {
    ST st;
    STInit(&st);

    while(*s)
    {
        if(*s=='{' || *s=='[' || *s=='(')
        {
            STPush(&st,*s);
        }
        else
        {
            if(STEmpty(&st))
            {
                STDestroy(&st);
                return false;
            }
            else{
                char top=STTop(&st);
                STPop(&st);
                if((*s==')' && top!='(')
                ||(*s=='}' && top!='{')
                ||(*s==']' && top!='['))
                {
                    STDestroy(&st);
                    return false;
                }
            }
        }
        s++;
    }

    bool ret=STEmpty(&st);
    STDestroy(&st);
    return ret ;
}

当然上面要有栈的功能为了方便你们查看我就截取了关键部分。

三.总结 

以上就是栈的知识点了，队列应该明天更新，如果对你有帮助，一键三连谢谢！若大佬发现错误一定要告诉我谢谢！感谢大家的阅读！