当前位置：首页 > news >正文

【数据结构 C语言版】第四篇栈、堆栈、Stack(超级详细版)

news 来源：原创 2024/4/29 8:58:58

【数据结构 C语言版】第四篇栈、堆栈、Stack

写在前面

更新情况记录：

最近更新时间	更新次数
2022/10/18	1

参考博客与书籍以及链接：
（非常感谢这些博主们的文章，将我的一些疑问得到解决。）

参考博客链接或书籍名称
《数据结构》陈越
代码随想录
总目录：目前数据结构文章太少，没有写。

正文

文章目录

【数据结构 C语言版】第四篇栈、堆栈、Stack
- 0.前置内容
- 1.栈的概念
- 2.栈的实现（顺序存储）
- - 2.1 栈的结构体
  - 2.2 栈的接口
  - 2.3 栈接口的实现
  - - 2.3.1 初始化栈
    - 2.3.2 入栈
    - 2.3.3 检测栈是否为空
    - 2.3.4 出栈
    - 2.3.5 获取栈顶元素
    - 2.3.6 获取栈中有效元素个数
    - 2.3.7 销毁栈
    - 2.3.8 打印栈
- 3.栈的题目(非编程题)

0.前置内容

如果你c语言还有困难的话，请看我的博客：

【十万字+详解C/C++】C/C++目录（持续更新）_潮.eth的博客-CSDN博客

关注我，不迷路。

1.栈的概念

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。

其实，我们日常生活中也可以看到堆栈的例子，比如，我们厨房中叠放的盘子，使用盘子（删除操作）时我们是从顶端拿走盘子，用完放回（插入操作）时也是放到顶端。

压栈：栈的插入操作叫做进栈（或者叫做压栈、入栈），入数据在栈顶。

出栈：栈的删除操作。出数据也在栈顶。

特点：后进先出，先进后出。

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

由于栈是线性表，因而栈的存储结构可采用顺序和链式两种方式。顺序存储的栈称为顺序栈，链式存储的栈称为链栈。

2.1 栈的结构体

typedef int STDatatype;
typedef struct Stack
{
    STDataType* a;//数组
    int top;//top-1就是栈顶的下标，a[top-1]就是栈顶元素
    int capacity;//代表栈的容量,表示能放多少数据
}

注意：我们这里用top-1来表示栈顶的下标。好处：top就是当前栈存放数据的个数，并且top==capacity时，说明栈已经满了要开辟数据。

2.2 栈的接口

// 1.初始化栈 
void StackInit(Stack* ps);
// 2.入栈 
void StackPush(Stack* ps, STDataType data);
// 3.出栈 
void StackPop(Stack* ps);
//4. 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 5.获取栈中有效元素个数 
int StackSize(Stack* ps);
// 6.检测栈是否为空，如果为空返回非零结果，如果不为空返回0 。布尔值也是可以的。
int StackEmpty(Stack* ps);
// 7.销毁栈 
void StackDestroy(Stack* ps);
//8.打印栈
void StackPrint(Stack* ps);

2.3 栈接口的实现

2.3.1 初始化栈

这里只需要把a置空，capacity跟top都置0就行。

void StackInit(Stack* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

2.3.2 入栈

分两种情况看：空间不够与空间足够。

空间不够时，top与capacity相等，当然top与capacity等于0的时候也算进去了。

空间足够时，直接赋值即可。

void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	//如果内存不够开辟新的内存空间
	if(ps->top==ps->capacity)
	{
        //假如capacity是0，那么就开辟4个空间,否则就开原来空间的2倍
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	//在后面添加数据.
	//这里的top-1才是栈顶元素的位置.
	ps->a[ps->top] = data;
	ps->top++;
}

还记得，为什么要开2倍吗？不会赶紧去看我的顺序表那章的博客吧。

2.3.3 检测栈是否为空

为了让出栈的代码写的方便些，我把检测栈是否为空放在前面。

检测栈是否为空，如果为空返回非零结果，如果不为空返回0 。布尔值也是可以的。

int StackEmpty(Stack* ps)
{
	assert(ps);
    //直接判断top是否为空，top实际充当了记录栈的个数的功能
	return (ps->top == 0);
}

2.3.4 出栈

首先判断栈是否为空。

然后top值减1即可。

这里无法部分释放内存，如果能就神奇了。

void StackPop(Stack* ps)
{
	assert(ps);
    //判断栈是否为空，为空就报错。
	assert(!StackEmpty(ps));
	--ps->top;
}

2.3.5 获取栈顶元素

注意：top-1才是栈顶的下标，当然你也可以设计成top是栈的下标，top+1代表栈的有效元素个数。

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}

2.3.6 获取栈中有效元素个数

注意：在这里top可以代表栈中有效元素的个数。

STDataType StackTop(Stack* ps)
{
    assert(ps);
	return ps->top;
}

2.3.7 销毁栈

开辟出的空间需要销毁，所以只需要销毁a。

其余参数置零即可。

void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);
	//为了保险起见，再赋值成NULL
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

2.3.8 打印栈

为了方便测试。

void StackPrint(Stack* ps)
{
	assert(ps);
	printf("栈的信息  top:%d  capacity:%d  \n",ps->top,ps->capacity);
	printf("栈打印: ");
	for (int i = 0; i < ps->top; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n\n");
}