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

数据结构之——栈的操作讲解与功能实现

news 来源：原创 2024/5/3 18:46:25

一.栈

A.栈的概念及结构

2.内存中栈区

B.栈的实现

1.实现方式：

2.栈的数据结构

3.栈的初始化

4.栈的销毁释放

5.栈数据的插入

6.空间检查

7.栈数据的删除——即出栈

8.访问栈区某个数据的函数

9.栈空间的长度函数

函数整体测试：

整体代码：

一.栈

A.栈的概念及结构

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

栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则，也可以叫后进先出。

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

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

注：这只是栈空间中数据大概的一个出入顺序，下图为详细的栈区增删。

2.内存中栈区

内存中的栈区空间是相当有限的，原因是内存大多空间都给了堆区，堆区是动态开辟的，空间分配的利用上比堆区要高很多，所以我们实现的大多程序都是动态开辟类型的。

栈区空间在内存是自顶向下开辟的：

正因为栈内存空间有限，那么在进行函数递归的时候，若是递归次数过多，会把栈空间放满从而系统会崩溃，崩溃的原因就是栈溢出（stack overflow) 例：

int f(int n) {
	return n == 1 ? 1 : f(n - 1) + f(n - 2);
}
int main() {
	printf("%d\n", f(10000));

	return 0;
}

测试结果：

B.栈的实现

1.实现方式：

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些，因为数组在尾上插入数据的代价比较小，而且CPU在数组上的高速缓存命中率比在链表上更高。所以下面我对于栈的实现方式是以顺序表为主体的。

对于顺序表的讲解和操作实现我已经写了一篇博客，地址在这： 数据结构——线性表之顺序表的基本操作讲解 大家想深入了解数据结构顺序表的实现可以看一看。

2.栈的数据结构

静态版：一般不用，空间固定，不灵活。

//静态不常用
typedef int STDataType;
#define N 100
struct Stack {
	STDataType a[N];
	int top;
};

动态版：比静态版的空间利用效率更高。

//动态
typedef int  STDataType;    //重定义int类型为栈类型的
typedef struct Stack {
	STDataType* a;	//栈型指针——指向堆区空间的
	int top;	//栈现有的个数
	int capacity;	//栈区的容量
}ST;    //将栈的结构体类型名改为ST，简化

3.栈的初始化

void StackInit(ST* ps)
{
	assert(ps);    //断言——判断实参传过来的指针是否为空
	ps->a = NULL;    //先暂时让栈的指针指向NULL
	ps->top = ps->capacity = 0;
}

4.栈的销毁释放

void StackDestroy(ST* ps)
{
	assert(ps);    
	free(ps->a);    //free掉动态开辟的空间
	ps->a = NULL;   //free掉空间后，这块堆区空间还在，只是还给了操作系统，而且栈的指针a还保存
                    //这块空间的地址，a成为了野指针，很危险，需要置为空
	ps->capacity = ps->top = 0;    //将容量和存储个数设为0

5.栈数据的插入

void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	// 扩容
	if (ps->top == ps->capacity)
	{
        //扩容一般扩2倍
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;

		STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity*sizeof(STDataType));
        
        //判断是否开辟成功，若开辟失败则报错
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

        //表示开辟失败
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
    
    //入栈，即在栈中存入要存的数据
	ps->a[ps->top] = x;
	ps->top++;    //栈空间的数据个数+1
}

注：栈的结构成员top表示栈中数据存储的个数，栈区为空时，Top指针指向栈底，因为顺序表是以数组为核心实现的，所以Top也就是数组的下标了。每存储一个数据Top都指向这个数据的下一个数据开始位置。

6.空间检查

在栈区空间的数据删除时，需要进行链表空间的判断，若栈空间为空，则不允许再删除了，所以要实现一个函数去检查。

注：VS中的C文件里，并不支持bool类型，所以需要在.c文件开头加入#include<stdbool.h>库函数。

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

7.栈数据的删除——即出栈

void StackPop(ST* ps)
{
	assert(ps);
    
    //判断栈区空间是否为空，若为空，则报错，不为空，则存储个数-1
	assert(!StackEmpty(ps));
	
	--ps->top;
}

栈的操作实现使用顺序表的原因：删除数据方式极为简单方便！

8.访问栈区某个数据的函数

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

刚才讲到了栈结构的成员变量top是从数组下标0开始访问的，访问到的数据，所得下标top要减一。

访问该数据时，函数返回的是Top指向的上一个数据的数值。

top-1原因：数据1，2，3，4，5入栈后，如下图：

当要访问数据4时，需要数据5出栈，才能访问到4，而top是下标，数据5对应的数组下标为4( top)，那么下标3 ( top-1）的位置就是数据4，所以return ps->a[ps->top-1] ; 数据4即可被访问到。

9.栈空间的长度函数

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

	return ps->top;
}

函数整体测试：

整体代码：

Test.c:

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"

void TestStack() {
	ST st;
	StackInit(&st);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	printf("%d\n", StackTop(&st));

	StackPop(&st);
	printf("%d\n", StackTop(&st));
	StackPop(&st);

	StackPush(&st, 4);
	StackPush(&st, 5);

	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	printf("\n");
}

//int f(int n) {
//	return n == 1 ? 1 : f(n - 1) + f(n - 2);
//}
int main() {
	//printf("%d\n", f(10000));
	TestStack();
	return 0;
}

Stack.c文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//初始化
void StackInit(ST* ps) {
	assert(ps);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

//入栈
void StackPush(ST* ps, STDataType x) {
	assert(ps);
	if (ps->top == ps->capacity) {
		//创建临时变量，若top==capacity说明两种情况
		//情况1：栈表刚开始，容量和数据个数都为0，先开个4字节的容量
		//情况2：说明栈的存储个数达到容量上限，需要扩容了
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		//上面这个语句设置了情况二所说的扩容倍数大小为2倍
		//扩容
		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
		if (tmp == NULL) {
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;

	}
	//将数据入栈
	ps->a[ps->top] = x;
	//个数+1
	ps->top++;
}

//出栈
void StackPop(ST* ps) {
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

//暴力检查
bool StackEmpty(ST* ps) {
	assert(ps);
	return ps->top == 0;
}
//计算栈表长度
int StackSize(ST* ps) {
	assert(ps);
	return ps->top;
}

//访问栈中某个数据
STDataType StackTop(ST* ps) {
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}

Stack.h文件：

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

//静态不常用
//typedef int STDataType;
//#define N 100
//struct Stack {
//	STDataType a[N];
//	int top;
//};

//动态
typedef int  STDataType;
typedef struct Stack {
	STDataType* a;	//栈型指针——指向堆区空间的
	int top;	//栈现有的个数
	int capacity;	//栈区的容量
}ST;

void StackInit(ST* ps);
void StackDestory(ST* ps);
void StackPush(ST* ps);
void StackPop(ST* ps);

bool StackEmpty(ST* ps);
int StackSize(ST* ps);
STDataType StackTop(ST* ps);

结论：数据结构建议不要直接访问数据，一定要通过函数接口访问（低耦合，高内聚）！！！