【数据结构】详解栈

今天我们主要来了解栈！如果对知识点有模糊，可翻阅以往文章哦！

个人主页：小八哥向前冲~-CSDN博客

所属专栏：数据结构【c语言版】_小八哥向前冲~的博客-CSDN博客

c语言专栏：c语言_小八哥向前冲~的博客-CSDN博客

值得注意的是，如果你十分了解顺序表和链表，今天这期会很轻松哦！

哈哈哈哈！当然，这期也能检测你对顺序表和链表的理解！一起看看吧！

目录

栈的定义

顺序表和链表的比较

栈的实现--顺序表

初始化

栈为空的判定

入栈

出栈

销毁

栈顶数据

数据个数

题目操练：配括号问题

栈的实现--链表

栈为空的判定

入栈

出栈

销毁

栈顶数据

数据个数

码源--栈（顺序表）

码源--栈（链表）

---

栈的定义

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

上图理解一下：

注意：遵循后进先出的原则！

知道了这个原则，我们来巩固一下：

1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出 栈的顺序是（ ）。

A .12345ABCDE

B.EDCBA54321

C.ABCDE12345

D.54321EDCBA

2.若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）

A.1,4,3,2

B.2,3,4,1

C.3,1,4,2

D.3,4,2,1

显然：1.B      2.C

相信第一题不难，我们解释一下第二题：看到C选项，1，2，3进栈后，3出栈，而第二次出栈的只能是2或4，不可能是1，所以C错误！

了解了栈的概念，我们实现这个栈是使用顺序表还是链表呢？

• 如果是顺序表的话，我们的栈顶应该要在数组末尾！如果在数组头部的话，数据进栈时还需要挪动其余数据以便数据的存入！效率很低！
• 如果是链表的话，我们的栈顶要在链表的头，入栈时，头插即可！如果栈顶在链表尾部的话，虽然入栈尾插即可，但需要遍历，效率低，那么这时就需要使用双链表！

综上所述，我们栈使用顺序表较好！(两种都实现看看)

上图看看它们：

为了更好透彻了解顺序表和链表，我们将它们比较看看！

顺序表和链表的比较

图文更加直观：

这里的缓存利用率不做过多解释，详情见：https://www.cnblogs.com/yungyu16/p/13054874.html

栈的实现--顺序表

既然是要在顺序表基础上实现栈，那么就要实现顺序表和栈的基本框架。

（单链表若有不懂的知识点，可见：通讯录的实现（顺序表版本）-CSDN博客）

stack.h文件--包含各种需要的函数

栈里面的变量：top表示栈顶下标，capacity表示栈空间。

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
 
typedef int STDateType;
//栈
typedef struct stack
{
	STDateType* a;
	int top;
	int capacity;
}ST;
 
//栈的初始化和销毁
void STInit(ST* p);
void STDestroy(ST* p);
//入栈，出栈
void STpush(ST* p,STDateType x);
void STpop(ST* p);
//栈顶的数据
STDateType STtop(ST* p);
//栈的数据个数
int STsize(ST* p);
//判空
bool STEmpty(ST* p);

接下来我们一一实现！

初始化

我们要将栈中各个变量进行初始化。

void STInit(ST* p)
{
	assert(p);
	p->a = NULL;
	p->capacity = 0;
	p->top = 0;
}

栈为空的判定

我们在实现这个函数时，很多人会用 if语句来判断是否为空，但我们仔细一想，可以好好优化一下代码！

//判空
bool STEmpty(ST* p)
{
	assert(p);
	return p->top == 0;
}

入栈

经过我们刚刚的分析，入栈要在数组尾部！记得每次入栈需要判断空间是否够用哦！

void STpush(ST* p, STDateType x)
{
	assert(p);
	if (p->top == p->capacity)
	{
		int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2;
		STDateType* tmp = (STDateType*)realloc(p->a, newcapacity * sizeof(STDateType));
		if (tmp == NULL)
		{
			perror("realloc failed!");
			return;
		}
		p->a = tmp;
		p->capacity = newcapacity;
	}
	p->a[p->top++] = x;
}

出栈

入栈要在尾部，出栈也要在尾部，后进先出的原则要时刻记住！

需要注意的是：当栈为空时，数据出不了栈！所以我们先需要判断是否为空！

void STpop(ST* p)
{
	assert(p);
	//出栈的话要判断一下空的情况
	assert(!STEmpty(p));
	p->top--;
}

销毁

我们既然用了开辟内存函数，当我们不使用栈时，要将空间释放掉！

void STDestroy(ST* p)
{
	assert(p);
	free(p->a);
	p->capacity = p->top = 0;
}

栈顶数据

在访问栈顶数据时，我们也要先判断栈是否为空，否则当栈为空时，访问栈顶数据便会越界访问！

//栈顶的数据
STDateType STtop(ST* p)
{
	assert(p);
	//出栈的话要判断一下空的情况
	assert(!STEmpty(p));
	return p->a[p->top-1];
}

数据个数

//栈的数据个数
int STsize(ST* p)
{
	assert(p);
	return p->top;
}

题目操练：配括号问题

既然我们已经实现的栈，我们来应用一下吧！

题目：详情--20. 有效的括号 - 力扣（LeetCode）

思路：

遍历数组，当是左括号时（"(","{","】"）时就入栈，当不是左括号时就出栈比较，直到遍历完成！

这样听是不是很简单呢？当然里面没有栈，我们需要将栈创建一下！

代码：

typedef char STDateType;
//栈
typedef struct stack
{
	STDateType* a;
	int top;
	int capacity;
}ST;
 
//栈的初始化和销毁
void STInit(ST* p);
void STDestroy(ST* p);
//入栈，出栈
void STpush(ST* p,STDateType x);
void STpop(ST* p);
//栈顶的数据
STDateType STtop(ST* p);
//栈的数据个数
int STsize(ST* p);
//判空
bool STEmpty(ST* p);
//栈的初始化和销毁
void STInit(ST* p)
{
	assert(p);
	p->a = NULL;
	p->capacity = 0;
	p->top = 0;
}
void STDestroy(ST* p)
{
	assert(p);
	free(p->a);
	p->capacity = p->top = 0;
}
//入栈，出栈
void STpush(ST* p, STDateType x)
{
	assert(p);
	if (p->top == p->capacity)
	{
		int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2;
		STDateType* tmp = (STDateType*)realloc(p->a, newcapacity * sizeof(STDateType));
		if (tmp == NULL)
		{
			perror("realloc failed!");
			return;
		}
		p->a = tmp;
		p->capacity = newcapacity;
	}
	p->a[p->top++] = x;
}
void STpop(ST* p)
{
	assert(p);
	//出栈的话要判断一下空的情况
	assert(!STEmpty(p));
	p->top--;
}
//栈顶的数据
STDateType STtop(ST* p)
{
	assert(p);
	//出栈的话要判断一下空的情况
	assert(!STEmpty(p));
	return p->a[p->top-1];
}
//栈的数据个数
int STsize(ST* p)
{
	assert(p);
	return p->top;
}
//判空
bool STEmpty(ST* p)
{
	assert(p);
	return p->top == 0;
}
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;
            }
            char top=STtop(&st);
            STpop(&st);
            if(top=='('&&*s!=')'
            ||top=='['&&*s!=']'
            ||top=='{'&&*s!='}')
            {
            STDestroy(&st);
            return false;
            }
        }
        s++;
    }
//当栈中没有左括号比较完时，便匹配不成
    bool ret=STEmpty(&st);
    STDestroy(&st);
    return ret;
}

可能有人说太麻烦了，但c语言中没有栈，只能自己创建哦！这是用目前c语言最简单的方法！

栈的实现--链表

和顺序表一样，我们首先要创建栈和链表的基本框架！

stack.h文件--包含需要的函数

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
 
typedef int STDataType;
//栈
typedef struct stack
{
	struct stcak* next;
	STDataType data;
}STNode;
 
 
//栈的销毁
void STDestroy(STNode* phead);
//入栈
void STpush(STNode** pphead,STDataType x);
//出栈
void STpop(STNode** pphead);
//栈顶数据
STDataType STtop(STNode* phead);
//判空
bool STEmpty(STNode* phead);
//栈数据个数
int STsize(STNode* phead);

栈为空的判定

有了顺序表的基础，接下来依葫芦画瓢----最简单不过！

//判空
bool STEmpty(STNode* phead)
{
	return phead == NULL;
}

入栈

我们分析将链表的头部为栈顶，进出都在头！（这种方案最佳！）

//创建节点
STNode* STBuyNode(STDataType x)
{
	STNode* node = (STNode*)malloc(sizeof(STNode));
	if (node == NULL)
	{
		perror("malloc failed!");
		return NULL;
	}
	node->data = x;
	node->next = NULL;
	return node;
}
 
//入栈
void STpush(STNode** pphead, STDataType x)
{
	STNode* node = STBuyNode(x);
	node->next = *pphead;
	*pphead = node;
}

出栈

将头节点指向下一个节点，原来的头节点释放！

//出栈
void STpop(STNode** pphead)
{
	assert(!STEmpty(*pphead));
	STNode* cur = *pphead;
	*pphead = (*pphead)->next;
	free(cur);
}

销毁

同样的，动态开辟了空间，当我们不用栈时，要将开辟的空间释放掉！

//栈的销毁
void STDestroy(STNode* phead)
{
	STNode* cur = phead;
	while (cur)
	{
		STNode* next = cur->next;
		free(cur);
		cur = next;
	}
}

栈顶数据

也是一样的，在访问栈顶数据时，要判断栈是否为空，防止越界访问！

//栈顶数据
STDataType STtop(STNode* phead)
{
	assert(!STEmpty(phead));
	return phead->data;
}

数据个数

遍历链表，将一个一个节点计数起来！

//栈数据个数
int STsize(STNode* phead)
{
	STNode* cur = phead;
	int count = 0;
	while (cur)
	{
		count++;
		cur = cur->next;
	}
	return count;
}

码源--栈（顺序表）

stack.h文件

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
 
typedef int STDateType;
//栈
typedef struct stack
{
	STDateType* a;
	int top;
	int capacity;
}ST;
 
//栈的初始化和销毁
void STInit(ST* p);
void STDestroy(ST* p);
//入栈，出栈
void STpush(ST* p,STDateType x);
void STpop(ST* p);
//栈顶的数据
STDateType STtop(ST* p);
//栈的数据个数
int STsize(ST* p);
//判空
bool STEmpty(ST* p);

stack.c文件

#include"stack.h"
//栈的初始化和销毁
void STInit(ST* p)
{
	assert(p);
	p->a = NULL;
	p->capacity = 0;
	p->top = 0;
}
void STDestroy(ST* p)
{
	assert(p);
	free(p->a);
	p->capacity = p->top = 0;
}
//入栈，出栈
void STpush(ST* p, STDateType x)
{
	assert(p);
	if (p->top == p->capacity)
	{
		int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2;
		STDateType* tmp = (STDateType*)realloc(p->a, newcapacity * sizeof(STDateType));
		if (tmp == NULL)
		{
			perror("realloc failed!");
			return;
		}
		p->a = tmp;
		p->capacity = newcapacity;
	}
	p->a[p->top++] = x;
}
void STpop(ST* p)
{
	assert(p);
	//出栈的话要判断一下空的情况
	assert(!STEmpty(p));
	p->top--;
}
//栈顶的数据
STDateType STtop(ST* p)
{
	assert(p);
	//出栈的话要判断一下空的情况
	assert(!STEmpty(p));
	return p->a[p->top-1];
}
//栈的数据个数
int STsize(ST* p)
{
	assert(p);
	return p->top;
}
//判空
bool STEmpty(ST* p)
{
	assert(p);
	return p->top == 0;
}

码源--栈（链表）

stack.h文件

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
 
typedef int STDataType;
//栈
typedef struct stack
{
	struct stcak* next;
	STDataType data;
}STNode;
 
 
//栈的销毁
void STDestroy(STNode* phead);
//入栈
void STpush(STNode** pphead,STDataType x);
//出栈
void STpop(STNode** pphead);
//栈顶数据
STDataType STtop(STNode* phead);
//判空
bool STEmpty(STNode* phead);
//栈数据个数
int STsize(STNode* phead);

stack.c文件

#include"stack.h"
 
STNode* STBuyNode(STDataType x)
{
	STNode* node = (STNode*)malloc(sizeof(STNode));
	if (node == NULL)
	{
		perror("malloc failed!");
		return NULL;
	}
	node->data = x;
	node->next = NULL;
	return node;
}
 
//入栈
void STpush(STNode** pphead, STDataType x)
{
	STNode* node = STBuyNode(x);
	node->next = *pphead;
	*pphead = node;
}
 
//出栈
void STpop(STNode** pphead)
{
	assert(!STEmpty(*pphead));
	STNode* cur = *pphead;
	*pphead = (*pphead)->next;
	free(cur);
}
 
//栈顶数据
STDataType STtop(STNode* phead)
{
	assert(!STEmpty(phead));
	return phead->data;
}
 
//判空
bool STEmpty(STNode* phead)
{
	return phead == NULL;
}
 
//栈数据个数
int STsize(STNode* phead)
{
	STNode* cur = phead;
	int count = 0;
	while (cur)
	{
		count++;
		cur = cur->next;
	}
	return count;
}
 
//栈的销毁
void STDestroy(STNode* phead)
{
	STNode* cur = phead;
	while (cur)
	{
		STNode* next = cur->next;
		free(cur);
		cur = next;
	}
}

是不是觉得今天的比较简单？好了，我们下期见！