[c语言日寄]数据结构：栈

【作者主页】siy2333
【专栏介绍】⌈c语言日寄⌋：这是一个专注于C语言刷题的专栏，精选题目，搭配详细题解、拓展算法。从基础语法到复杂算法，题目涉及的知识点全面覆盖，助力你系统提升。无论你是初学者，还是进阶开发者，这里都能满足你的需求！
【食用方法】1.根据题目自行尝试 2.查看基础思路完善题解 3.学习拓展算法
【Gitee链接】资源保存在我的Gitee仓库：https://gitee.com/siy2333/study

---

---

前言：

在计算机科学中，数据结构是组织和存储数据的方式，而栈（Stack）是其中一种非常基础且重要的数据结构。它遵循后进先出（Last In First Out，LIFO）的原则，就像一叠盘子，你只能在最上面添加或移除盘子。本文将深入探讨栈的原理、实现方式以及应用场景，帮助读者更好地理解和运用这一数据结构。

文末附带完整的带有标准注释的c语言头文件以及源文件。

---

栈的基本概念

栈是一种线性数据结构，它只允许在表的一端进行插入和删除操作。这一端被称为栈顶（Top），而另一端被称为栈底（Bottom）。栈的基本操作包括：

1. 入栈（Push）：将一个元素添加到栈顶。
2. 出栈（Pop）：移除栈顶的元素。
3. 查看栈顶元素（Top）：获取栈顶元素的值，但不移除它。
4. 检查栈是否为空（Empty）：判断栈中是否还有元素。
5. 获取栈的大小（Size）：返回栈中元素的数量。

这些操作的实现方式会因具体的编程语言和数据结构设计而有所不同，但基本原理是一致的。

栈的实现

栈可以通过数组或链表来实现。在本文中，我们将重点介绍基于数组的栈实现，因为它更简单且易于理解。以下是基于数组的栈实现的关键点：

初始化

在使用栈之前，需要对其进行初始化。这通常包括分配内存空间、设置栈顶指针和栈的容量。在我们的代码示例中，栈的初始化函数STInit会为栈分配初始容量为4的内存空间，并将栈顶指针设置为0。

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; // The next position of the current stack top elementreturn;
}

入栈

当向栈中添加元素时，需要检查栈是否已满。如果栈已满，则需要扩容。扩容通常是通过分配更大的内存空间来实现的。在我们的代码中，当栈满时，会将栈的容量加倍。

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

出栈

出栈操作相对简单，只需要将栈顶指针减1即可。但在出栈之前，需要检查栈是否为空，以避免出现错误。

void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;return;
}

查看栈顶元素

查看栈顶元素的操作也很简单，只需要返回栈顶指针所指向的元素即可。同样，在执行此操作之前，需要检查栈是否为空。

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

检查栈是否为空

检查栈是否为空的操作可以通过比较栈顶指针是否为0来实现。

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

获取栈的大小

获取栈的大小的操作可以通过返回栈顶指针的值来实现。

int STSize(ST* ps)
{assert(ps);return ps->top;
}

销毁栈

在使用完栈后，需要对其进行销毁，以释放分配的内存空间。销毁栈的操作包括释放内存空间、将栈顶指针和容量设置为0。

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

栈的应用场景

栈在计算机科学中有着广泛的应用，以下是一些常见的应用场景：

函数调用

在编程语言中，函数调用是通过栈来实现的。当一个函数被调用时，它的参数、返回地址和局部变量等信息会被压入调用栈中。当函数执行完毕后，这些信息会被弹出栈，程序会返回到调用函数的位置继续执行。

表达式求值

栈可以用于表达式的求值。例如，在计算后缀表达式时，可以使用一个栈来存储操作数。当遇到一个操作符时，从栈中弹出两个操作数，进行相应的运算，然后将结果压入栈中。当表达式计算完毕时，栈顶的元素就是表达式的值。

括号匹配

栈可以用于检查括号是否匹配。当遇到一个左括号时，将其压入栈中；当遇到一个右括号时，从栈中弹出一个左括号。如果在弹出左括号时栈为空，或者弹出的左括号与右括号不匹配，则说明括号不匹配。

浏览器的前进和后退功能

浏览器的前进和后退功能也可以通过栈来实现。当用户访问一个网页时，将该网页的地址压入一个栈中；当用户点击后退按钮时，从栈中弹出一个网页地址并跳转到该网页；当用户点击前进按钮时，将弹出的网页地址压入另一个栈中。

栈的优缺点

栈的优点包括：

1. 简单易用：栈的实现相对简单，操作也容易理解。
2. 高效：栈的基本操作（如入栈、出栈、查看栈顶元素等）的时间复杂度为O(1)。
3. 适用范围广：栈在计算机科学中有着广泛的应用，如函数调用、表达式求值、回溯算法等。

然而，栈也有一些缺点：

1. 容量限制：如果栈的容量有限，可能会出现栈溢出的情况。虽然可以通过动态扩容来解决这个问题，但动态扩容会增加时间和空间的开销。
2. 只能在一端操作：栈只能在栈顶进行插入和删除操作，不能在其他位置进行操作。

栈的优化

虽然栈的基本操作已经非常高效，但在某些情况下，我们仍然可以通过一些优化手段来提高栈的性能。以下是一些常见的优化方法：

预分配内存

在初始化栈时，可以预分配一定量的内存空间，以减少动态扩容的次数。这可以提高栈的性能，但会增加内存的使用量。

使用循环缓冲区

循环缓冲区是一种特殊的数组结构，它可以循环使用内存空间。通过使用循环缓冲区，可以减少内存的分配和释放次数，从而提高栈的性能。

栈的测试

为了验证栈的正确性和性能，我们需要对其进行测试。以下是一个简单的测试程序，用于测试栈的基本操作：

#include"Stack.h"void Test1()
{ST head;STInit(&head);STPush(&head, 1);STPush(&head, 2);STPush(&head, 3);STPush(&head, 4);STPush(&head, 5);while (!STEmpty(&head)){printf("%d ", STTop(&head));STPop(&head);}printf("\n");return;
}int main()
{Test1();return 0;
}

在这个测试程序中，我们首先初始化了一个栈，然后依次向栈中添加了5个元素。接着，我们依次从栈中弹出元素，并打印出每个元素的值。最后，我们销毁了栈。

完整代码

头文件

#pragma once/**
* @file Stack.h
* @brief The header file of the Stack.
* @author siy2333
* @date 2025.5.11
*
* This header file defines the data structure and related operation functions of a Stack.
* Stack is a Last-In-First-Out (LIFO) data structure used for storing and managing data elements, supporting operations to add (push) and remove (pop) elements at the top, and is widely applied in program calling, expression evaluation, and other scenarios.
* Provides basic operations for adding, deleting, querying, and modifying.
*///Standard library header files included.
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>/**
* @brief The data types stored in the Stack.
*/
typedef int STDataType;/**
* @typedef struct Stack.
* @brief Structure definition of Stack.
*/
typedef struct Stack
{STDataType* a;		///< The pointer to the memory for the Stack.int top;			///< The next position of the current Stack top element.int capacity;		///< The size of capacity.
}ST;/**
* @brief Initialize Stack.
*/
void STInit(ST* ps);/**
* @brief Destory the Stack.
*/
void STDestory(ST* ps);/**
* @brief Store x in the top of the Stack.
*/
void STPush(ST* ps, STDataType x);/**
* @brief Delete x at the top of the Stack.
*/
void STPop(ST* ps);/**
* @brief return the capacity size of the Stack.
*/
int STSize(ST* ps);/**
* @brief Check whether the Stack is empty.
* @return If the Stack is empty, return 1; Otherwise, return 0.
*/
bool STEmpty(ST* ps);/**
* @brief Return the data at the top of the Stack.
* @return the data at the top of the Stack.
*/
STDataType STTop(ST* ps);

源文件

#include"Stack.h"/**
* @detailsThe faction use malloc to apply for 4 copies of memory for the Stack.The 0 will be store int the ps->top, it mean the next position of the current stack top element.The capacity will be set to 4.
* @warning ps mustn't be NULL.
*/
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;		//The next position of the current stack top elementreturn;
}/**
* @details The faction will free the memory for the Stack;The top will be set to 0;The capacity will be set to 0.
* @warning ps mustn't be NULL.
*/
void STDestory(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = 0;ps->capacity = 0;return;
}/**
* @details The faction will check whether the Stack is full;If the Stack is full, it will use realloc() to double the capacity, and refresh the ps->capacity.It will store the x in the ps->a[top], and refresh the ps->top.
* @warning ps mustn't be NULL.
*/
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->capacity == ps->top){STDataType* point = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity * 2);if (point == NULL){perror("realloc fail");return;}ps->a = point;ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++;return;
}/**
* @details The function will refresh the ps->top.
* @warning ps musn't be NULL;
* @warning The Stack mustn't be empty.
*/
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;return;
}/**
* @warning ps mustn't be NULL;
*/
int STSize(ST* ps)
{assert(ps);return ps->top;
}/**
* @warning ps mustn't be NULL;
*/
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}/**
* @warning ps musn't be NULL;
* @warning The Stack mustn't be empty.
*/
STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}

栈的总结

栈是一种非常基础且重要的数据结构，它遵循后进先出的原则。栈的基本操作包括入栈、出栈、查看栈顶元素、检查栈是否为空和获取栈的大小等。栈可以通过数组或链表来实现，其中基于数组的栈实现相对简单且易于理解。栈在计算机科学中有着广泛的应用，如函数调用、表达式求值、回溯算法等。虽然栈有一些缺点，但它的优点使其在许多场景下都非常有用。通过一些优化手段，我们可以进一步提高栈的性能。总之，栈是一种非常重要的数据结构，值得我们深入学习和研究。

希望本文对您理解栈有所帮助。如果您有任何问题或建议，欢迎在评论区留言讨论。

[专栏链接QwQ] :⌈c语言日寄⌋CSDN
[关注博主ava]：siy2333
感谢观看~ 我们下次再见!!