作者：几冬雪来

时间：2023年3月18日

内容：数据结构栈和队列的基础讲解

目录

前言： 

1.栈的概念及结构： 

2.栈的插入和删除：

3.栈的实现：

1.创建文件：

2.静态栈的实现： 

3.栈的结构体：

4.栈的初始化： 

5.释放栈： 

6.扩容操作： 

7.取出栈顶元素： 

8.返回下标个数：

9.访问栈顶元素： 

10.实践：

11.代码： 

 结尾：

---

前言： 

在这篇博客之前，我们将数据结构中的链表部分内容讲解完毕，那么在链表完结后，我们又很快进入数据结构中的另一个板块的学习了，板块名为——栈和队列。

1.栈的概念及结构： 

既然这一篇讲述的内容是栈与队列，那么一开始我们就要先了解它们是什么东西。首先来说一说——栈。 

栈：栈是一种特殊的线性表，先比较与链表的可以进行头插或者尾插操作不一样，它只允许进行固定一端的插入或者删除元素的操作，栈中的数据元素遵守后进先出的原则，插入元素的操作我们称为——入栈/压栈/进栈，删除元素的操作被我们称为——出栈。

2.栈的插入和删除：

了解到了栈基本信息后，这里我们就画一个图来讲解一下栈的插入和删除。

这就是我们的入栈和出栈的原理图。从图可以看出，在栈中进行数据插入和删除操作的一端被我们称为栈顶，出数据和入数据都在栈顶进行，这也符合我们后进先出的原则。

这里我们依靠栈来举例子，正常来说我们往栈里面插入数据1,2,3，到时候栈里面进行删除的话就是反过来3,2,1的依次删除。 

那么这里问一个问题，我们的栈的出栈形式只有这一种固定的结果吗？那肯定不是的，栈的入栈和出栈形式有很多种，而它们的结果也不一样。

依旧以1,2,3来举例，我们先依次进栈，再依次出栈，这是我们的一种结果。

类似我们上图就是另外一种结果，入栈同样是1,2,3。但是这次我们不再全部入栈完再依次出栈，在这里我们对一个值先入栈后执行出栈的操作，然后接下来再入栈另一个值。这种一边入栈一边出栈的操作，最后我们的结果不是3,2,1而是1,2,3。同时这里也可以变为先入栈1,2，然后2进行出栈操作，下来再入栈3，最后全部出栈，这又是一种新的结果。

3.栈的实现：

讲了那么多栈的基本内容，接下来我们就来实现栈。而在我们的数据结构中，数组和链表都可以用作栈的实现。而在实现栈的过程中，在前面两者之间我们优先使用数组形式。因为对比链表，数组中的元素是连续的，也比较符合我们上方栈的图像。

1.创建文件：

栈的实现和我们的顺序表与链表一样，一开始都是要创建多个文件。

这里还是创建一个.h文件和两个.c文件。 

2.静态栈的实现： 

因为在栈的实现中我们优先选取的是数组形式，那么这里就延伸出来了——静态栈这一个操作，那么我们的静态栈又是怎么实现的？ 

在这里简简单单进行一个初始化，因为是多个变量，因此我们还是创建一个结构体来保存我们的数据。 

在结构体我们我们创建一个数组来存放我们的元素，top为我们的下标，capacity为我们元素的个数。 

3.栈的结构体：

但是在日常中，我们并不怎么使用静态的栈。那么不用数组初始化而是用指针初始化我们的结构体代码需要怎么修改一下呢？

与上面相同，op为我们的下标，capacity为我们元素的个数，只不过这里将原先的数组替换成为了指针。 

4.栈的初始化： 

栈的结构体书写完了之后，接下来要对其进行使用的话，首先就要对其初始化，那它是怎么样初始化的呢？ 

 

这里在一开始我们就断言，而后先为我们的栈开辟一块空间，如果开辟失败我们这里要进行一个报错提醒。既然开辟了4个整形大小，那么capacity元素的个数也要初始化为4，top对应下标初始化为0。 

5.释放栈： 

既然我们要使用栈的话，在使用之后将其释放也是我们必不可少的一个步骤。 

 

这里也是非常的简单，直接free掉a然后将其置空，又因为置空了，所以这里的capacity和top都要改为0。 

6.扩容操作： 

既然我们上面在进行初始化的时候用到了malloc函数，那么肯定就存在着内存不够需要扩容的情况。 

 

还是断言先，接下来判断，如果我们下标的值和capacity相等，说明我们的空间满了需要对其扩容。扩容的代码就不多讲了，如果扩容成功的话这里就将新创建的指针交给ps->a进行维护，又因为扩容了原先的两倍所以capacity乘等于2。如果不需要扩容的话，这里就将x的值给数组下标为ps->top的位置，然后ps->top进行++即可。

7.取出栈顶元素： 

在前面提到了，有入栈的操作那自然也会有出栈的操作。这个操作也就类似我们删除数组的尾元素。 

 

 

这里需要两个断言，一个来判断ps为不为空，另一个则是用来判断我们的下标，如果ps->top不为0则不会报错，如果二者都为真的话，我们这里直接让ps->top--即可，并不用将它释放置空。 

8.返回下标个数：

如果这里我们要查在这里我们应该有多少个元素的话该怎么办？

 

这里也是十分的简单，直接断言后返回即可。 

9.访问栈顶元素： 

如果我们要打印数据的话，那就要一个一个的访问栈顶的元素，而后将栈顶的元素删除。 

 

因为在之前的程序中，我们将ps->top加到了栈顶的下一个位置，所以这里需要进行-1操作才能访问我们栈顶的元素。开始依旧要进行断言操作。

10.实践：

在这里我们输入几个值来实现一下操作。

 

这种就是我们的依次入栈完了之后再依次出栈的操作结果。如果我们想要里面某个值入栈后马上进行出栈的操作又要怎么搞？

 

11.代码： 

Stack.c文件

#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->capacity = 4;
	ps->top = 0;//top栈顶元素的下一个位置
	//ps->top = -1;top栈顶元素的位置
}

//释放栈
void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

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

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

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

	ps->top--;
}

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

	return ps->top;
}

bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

STDataType STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	return ps->a[ps->top - 1];
}

 Sack.h文件

#pragma once

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

typedef int STDataType;

#define N 10

typedef struct Stack
{
	int *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);

test.c文件

#include "Stack.h"

int main()
{
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	printf("%d ", STTop(&st));
	STPop(&st);
	STPush(&st, 3);
	STPush(&st, 4);
	printf("%d ", STTop(&st));
	STPop(&st);
	STPush(&st, 5);

	while (!STEmpty(&st))
	{
		printf("%d ", STTop(&st));
		STPop(&st);
	}

	STDestroy(&st);
	return 0;
}

 结尾：

到这里，我们栈的基础操作就已经实现和书写完毕了，但是这并不是结束，接下来我们还会对栈进行更加深入的了解和学习。在往后的一些题目当中，有一些也会用到我们栈与队列的知识去解决，最后希望这篇博客可以为各位栈与队列的部分的学习开一个头。