探寻栈的奇妙世界

目录

引言

栈的概念及结构

栈接口实现

结构

初始化 

 入栈

出栈

 取栈顶

判空 

数据个数

释放

总结

引言

欢迎来到我的博客，今天我们将一起探索程序设计中一个不可或缺的数据结构 — 栈。在这篇博客中，我将为你揭开栈的神秘面纱，从栈的基本概念开始，一起探讨其背后的原理。我们将不仅限于理论，更将通过实际接口的实现，让你亲身感受栈的各种操作具体实现方式，最终轻松手撕一个栈。让我们一起踏上栈的探索之旅吧！

栈的概念及结构

栈（Stack）是一种特殊的线性表，它基于后进先出（Last In, First Out，LIFO）的原则。栈可以看作是一系列元素的集合，其中元素的插入和删除操作仅在栈的一端进行，通常称为栈顶，另一端则称为栈底。栈提供了两个主要的操作：
入栈（Push）： 将元素添加到栈的顶部，即插入操作。
出栈（Pop）： 从栈的顶部移除元素，即删除操作。

如图所示，最后入栈的元素在栈的顶端，所以在栈中，最后一个入栈的元素是第一个出栈的。

栈可以用数组或链表来实现。使用数组来实现的话，我们需要让数组的尾部为栈顶，这样只需要涉及到数组的尾插尾删，我们知道数组的尾插尾删效率是很高的。而如果选择链表实现的话，就需要让链表的头部作为栈顶，因为单向链表的尾插尾删涉及到找尾，效率不高。当然，可以选择使用双向循环链表或者在使用单向链表的基础上同时维护一个头指针和一个尾指针，这样的话首尾任选一端做栈顶即可。本篇博客，我们以数组栈来讲解栈涉及到的操作，当然，实现的是动态栈。


数组实现如上


链表实现如上

栈接口实现

结构

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

typedef int STDataType;

typedef struct Stack
{
	STDataType* data;
	int Top;       // 栈顶
	int capacity;  // 容量
}Stack;

可以看到这个结构与顺序表的很类似，只是栈这里用的是Top，事实上和顺序表那里的size的作用是类似的，这里的Top也是表示当前最后一个数据的下一个位置的下标，当栈为空时，Top的值为0

初始化 

void StackInit(Stack* ps)
{
	assert(ps);

	ps->capacity = 0;
	ps->data = NULL;
	ps->Top = 0;
}

初始化的时候给不给空间都行。我这里的Top是用来指向最后一个数据的下一个位置，如果想让Top就是最后一个数据的下标位置的话，初始化的时候就要让Top为-1。不同的Top在接下来的插入、取栈顶元素和判空等操作在代码上都会有一些细微的差异。 


 

 入栈

void StackPush(Stack* ps, STDataType val)
{
    assert(ps);  // 断言栈结构非空

    // 检查是否需要扩容
    if (ps->capacity == ps->Top)
    {
        // 计算新容量
        int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        
        // 重新分配内存空间
        STDataType* tmp = (STDataType*)realloc(ps->data, sizeof(STDataType) * newcapacity);
        if (tmp == NULL)
        {
            perror("realloc fail");  // 输出错误信息
            exit(-1);  // 退出程序，表示内存分配失败
        }
        
        // 更新栈的容量和数据存储区域
        ps->capacity = newcapacity;
        ps->data = tmp;
    }

    // 将元素添加到栈顶，并更新栈顶位置
    ps->data[ps->Top] = val;
    ps->Top++;
}

首先，通过断言确保栈结构非空，然后检查栈是否需要扩容。如果当前栈的容量等于栈顶位置，就进行动态内存扩容，如果容量是0的话，就设置为4，否则将栈的容量翻倍。接着，通过 realloc 函数进行扩容操作，如果内存分配失败，输出错误信息并退出程序。最后，将要入栈的元素添加到栈顶，并更新栈顶位置。如果Top设置为-1的话，这里就是先让Top加加，再来添加元素。

出栈

void StackPop(Stack* ps)
{
    assert(ps);          // 断言栈结构非空
    assert(ps->Top > 0); // 断言栈顶位置大于0，确保栈非空

    ps->Top--;           // 将栈顶位置减一，实现出栈操作
}

首先，通过断言确保栈结构非空。然后，再次通过断言确保栈顶位置大于0，以确保栈非空，因为不能从空栈中执行出栈操作。最后，将栈顶位置减一，实现出栈操作，即从栈中移除元素。 

 取栈顶

STDataType StackTop(Stack* ps)
{
    assert(ps);                    // 断言栈结构非空
    assert(ps->Top > 0);           // 断言栈顶位置大于0，确保栈非空

    return ps->data[ps->Top - 1];  // 返回栈顶元素，不改变栈的状态
}

首先，通过断言确保栈结构非空并且栈顶位置大于0，因为不能在空栈中执行获取栈顶元素的操作。最后，通过 ps->Top - 1 访问栈顶位置上的元素，并将其返回。如果Top初始化的时候设置成-1，这里就不需要减去1。

判空 

bool StackEmpty(Stack* ps)
{
    assert(ps);              // 断言栈结构非空

    return ps->Top == 0;     // 返回栈顶位置是否为0，判断栈是否为空
}

同理，Top设置为-1的话，这里栈为空的条件就要变成Top为-1。 

数据个数

int StackSize(Stack* ps)
{
    assert(ps);         // 断言栈结构非空

    return ps->Top;     // 返回栈顶位置，即栈的当前大小
}

Top设置为-1的话，返回的Top值需要加一。

释放

void StackDestroy(Stack* ps)
{
    assert(ps);         // 断言栈结构非空

    free(ps->data);     // 释放栈的数据存储区域的动态分配内存
    ps->data = NULL;    // 将数据存储区域指针置为NULL，防止悬空指针问题
    ps->capacity = 0;   // 将栈的容量设为0，表示没有分配内存
    ps->Top = 0;        // 将栈顶位置设为0，表示栈中没有元素
}

这里使用 free 函数释放栈的数据存储区域的动态分配内存。接着，将数据存储区域指针置为空，以防止悬空指针(野指针)问题。最后，将栈的容量设为0，表示没有分配内存，同时将栈顶位置设为0，表示栈中没有元素。 

总结

通过这篇博客，我们探讨了栈这一重要的数据结构，了解了栈的概念及结构。从栈的基本概念入手，我们逐步展开，详细介绍了栈接口的实现。在结构方面，我们深入研究了栈的初始化、入栈、出栈、取栈顶、判空、数据个数以及释放等关键操作。通过实际的接口实现，读者能够清晰地了解栈的内部机制，读者可以自己实现一下这些接口来加深对栈的理解，或者在力扣上刷上几道栈相关的题目。