重生之我在异世界学编程之数据结构与算法：深入栈篇

大家好，这里是小编的博客频道
小编的博客：就爱学编程

很高兴在CSDN这个大家庭与大家相识，希望能在这里与大家共同进步，共同收获更好的自己！！！

那接下来就让我们开始遨游在知识的海洋！

一、引言

栈（Stack）是一种常见的数据结构，具有后进先出（LIFO, Last In First Out）的特性。数组栈则是使用数组来实现栈这种数据结构的一种方式。本文将详细介绍数组栈的基本概念、实现方法以及应用场景。

二、基本概念

2.1 栈的定义与特性

• 定义：栈是一种特殊的线性表，其只允许在表的一端进行插入和删除操作。这一端被称为栈顶（Top），另一端则称为栈底（Bottom）。
• 特性：后进先出（LIFO），即最后插入的元素最先被删除。

2.2 数组栈的实现原理

数组栈利用数组的连续存储空间来存储栈中的元素。通过维护一个栈顶指针（Top Pointer）来指示当前栈顶的位置。当有新元素入栈时，栈顶指针增加；当有元素出栈时，栈顶指针减少。

三、数组栈的实现

3.1 数据结构设计

定义一个结构体来表示数组栈，包括数组本身、栈的大小、栈顶指针等成员变量。

typedef struct {
    int data[MAX_SIZE];  // 存储栈元素的数组
    int top;             // 栈顶指针
    int maxSize;         // 栈的最大容量
} ArrayStack;

3.2 基本操作实现

3.2.1 初始化栈

 
void initStack(ArrayStack *stack, int size) {
    stack->maxSize = size;
    stack->top = -1;  // 初始时栈为空，栈顶指针为-1
}
 

3.2.2 判断栈是否为空

 
bool isEmpty(ArrayStack *stack) {
    return stack->top == -1;
}

3.2.3 判断栈是否满

 
bool isFull(ArrayStack *stack) {
    return stack->top == stack->maxSize - 1;
}

3.2.4 入栈操作

bool push(ArrayStack *stack, int value) {
    if (isFull(stack)) {
        return false;  // 栈满，无法入栈
    }
    stack->data[++stack->top] = value;
    return true;
}

3.2.5 出栈操作

 
bool pop(ArrayStack *stack, int *value) {
    if (isEmpty(stack)) {
        return false;  // 栈空，无法出栈
    }
    *value = stack->data[stack->top--];
    return true;
}

3.2.6 获取栈顶元素

 
bool peek(ArrayStack *stack, int *value) {
    if (isEmpty(stack)) {
        return false;  // 栈空，无法获取栈顶元素
    }
    *value = stack->data[stack->top];
    return true;
}

四、数组栈的应用场景

4.1 函数调用管理

在计算机系统中，函数调用栈（Call Stack）通常使用数组栈来实现。每当函数被调用时，其返回地址和相关参数被压入栈中；当函数执行完毕后，再从栈中弹出这些信息以返回到调用者。

4.2 表达式求值

在编译器设计中，数组栈常用于表达式的求值过程。例如，后缀表达式（逆波兰表示法）可以通过一个简单的数组栈来高效地计算其结果。

4.3 括号匹配检查

在处理编程语言中的代码或文本编辑器的自动补全功能时，可以使用数组栈来检查括号的匹配性。每遇到一个左括号就压入栈中，遇到右括号则从栈中弹出一个左括号进行检查。

4.4 路径导航与历史记录

在图形界面应用程序中，如浏览器、文件管理器等，可以使用数组栈来保存用户的导航历史记录。当用户前进或后退时，可以从栈中弹出或压入相应的页面或目录信息。

五、源码

ST.h

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

#define MAXCAPACITY 4

typedef int Datastyle;

typedef struct stack {
	Datastyle* a;               //指向有效数据的指针 
	int top;
	//给top初始化一般要么给-1，要么给0，如果给1及以上就会造成空间的浪费，给-2及以下也会造成空间的浪费（除非进行特殊的处理，分情况给top加值）
	//如果top初始化给的是-1，则top代表的是栈顶元素所在位置的下标；如果top初始化给的是0，则top代表的是栈顶元素所在位置的下一个位置的下标
	//这是因为（以插入为例）每一次入栈后，top必定加1-----而top初始化给-1元素入栈就是top先++再赋值；而top初始化给0元素入栈就是top先赋值再++
	//但无论哪种入栈方式，最终的结果都是top++。至于为什么两种不同的给top赋初值对应不同的入栈方式也是取决于数组的下标从0开始的特点
	//本次我们就展示top初始化为0的栈的写法
	int capacity;
}ST;

ST.c

#include"ST.h"

//初始化栈
void STInit(ST* ps) {
	assert(ps);
	Datastyle* temp = (Datastyle*)malloc(MAXCAPACITY * sizeof(Datastyle));
	if (temp == NULL) {
		perror("malloc fail");
		exit(-1);
	}
	ps->a = temp;
	ps->capacity = MAXCAPACITY;
	ps->top = 0;
}

//销毁栈
void  STDestory(ST* ps){
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

//插入数据（从栈顶）----（入栈，压栈）
void STPush(ST* ps, Datastyle x) {
	assert(ps);
	//判断是否满了
	if (ps->top == ps->capacity) {
		Datastyle* temp = (Datastyle*)realloc(ps->a, 2 * ps->capacity * sizeof(Datastyle));				//扩容为当前容量的两倍比较合理
		if (temp == NULL) {
			perror("realloc fail");
			return;
		}
		ps->capacity *= 2;
		ps->a = temp;
	}
	ps->a[ps->top++] = x;
}

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

//删除数据（从栈顶）----（出栈）
void STPop(ST* ps) {
	assert(ps && !STEmpty(ps));
	--ps->top;
}

//访问栈顶元素
Datastyle STTop(ST* ps) {
	return ps->a[ps->top - 1];
}

//得出栈的元素个数
int STSize(ST* ps) {
	assert(ps);
	return ps->top;
}

Test.c

#include"ST.h"
void test1() {
	ST st;
	//初始化栈
	STInit(&st);

	//插入数据（从栈顶）----（入栈，压栈）
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	STPush(&st, 5);
	//我们要是想访问栈里的全部元素只能一直访问栈顶元素并在每一次访问后把栈顶元素删除（这是由栈的性质决定的）
	while (!STEmpty(&st)) {
		printf("%d ", STTop(&st));
		STPop(&st);
	}
	printf("\n");

	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	STPush(&st, 5);
	//删除数据（从栈顶）----（出栈）
	STPop(&st);
	STPop(&st);
	STPop(&st);
	STPop(&st);

	//访问栈顶元素
	Datastyle ret1 =  STTop(&st);
	printf("%d\n", ret1);                           //这里的占位符取决于我们存储的有效数据类型

	//得出栈的元素个数
	int ret2 = STSize(&st);
	printf("%d\n", ret2);						   //这里的占位符与我们存储的有效数据类型无关，仅仅是因为个数一般就为整形	

	//销毁栈
	STDestory(&st);
}

int main() {
	test1();
	return 0;
}

六、总结与展望

本文详细介绍了数组栈的基本概念、实现方法以及应用场景。数组栈作为一种简单而有效的数据结构，在许多领域都有着广泛的应用。随着计算机技术的不断发展，数组栈的实现和优化也将继续得到深入的研究和探索。

快乐的时光总是短暂，咱们下篇博文再见啦！！！不要忘了，给小编点点赞和收藏支持一下，在此非常感谢！！！