数据结构：栈和队列（Stack篇）（简单易懂超详细）

数据结构：栈和队列（Stack篇）（简单易懂超详细）

引用

CSDN

1.

https://blog.csdn.net/Jdxxwu/article/details/142314129

栈是数据结构中一种重要的线性表，其只允许在固定的端进行插入和删除元素操作。本文将详细介绍栈的概念、实现方式以及相关操作的代码示例。

前言

今天我们一起来实现数据结构中的栈。

一、栈是什么？

1. 栈的概念

栈：一种特殊的线性表，其只允许在固定的端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
栈就像是一叠盘子，我们放盘子只能放到盘子的最上面，同理取盘子，也只能从栈的最上方来取。放盘子称为入栈，去盘子称为出栈。

2.栈的结构选择

栈底层结构选型：
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

下面我们来对比一下这几种实现：

二、栈的实现

1. 栈结构体的定义

基于下面这张图，再类比顺序表，我们可以发现，栈的实现需要三个元素。

typedef int STDataType;
typedef struct Stack
{
    STDataType* arr;        //栈数组
    int capacity;           //栈的空间大小
    int top;                //栈顶位置
}ST;

2. 栈的初始化

//栈的初始化
void STInit(ST* ps);

我们需要将arr ， capacity ， top这三个元素初始化。具体的实现是：

//栈的初始化
void STInit(ST* ps)
{
    assert(ps);
    ps->arr = NULL;
    ps->capacity = 0;
    ps->top = 0;
}

3. 栈的销毁

有初始化必然有销毁。

//栈的销毁
void STDestroy(ST* ps);

我们需要释放栈中的空间，别忘了将其置为NULL。释放掉栈中所有的元素。

//栈的销毁
void STDestroy(ST* ps)
{
    assert(ps);
    if(ps->arr)
    free(ps->arr);
    ps->arr = NULL;
    ps->capacity = 0;
    ps->top = 0;
}

3. 入栈

//数据入栈
void StackPush(ST* ps, STDataType x); //STDataType x 是我们需要插入的数据

在入栈之前我们需要判断数组容量够不够，需不需要扩容。具体实现是

//数据入栈
void StackPush(ST* ps, STDataType x)
{
    assert(ps);
    if (ps->capacity == ps->top)           //空间满了需要扩容
    {
        int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;  //三目运算符如果原本栈为空，就赋初始为4个空间，若不为空，则双倍扩容
        STDataType* tem = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType));
        //判断所开空间是否成功
        if (tem == NULL)
        {
            perror("realloc fail!");
            exit(1);
        }
        ps->arr = tem;
        ps->capacity = newcapacity;
    }
    //入栈开始
    ps->arr[ps->top++] = x;
}

4.出栈

注意，如果栈为空，则不能出数据。因此先写判空方法。注意包含头文件
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h>

//数据出栈
void StackPop(ST* ps);

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

开始出栈

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

5. 取栈顶元素

//取栈顶元素
STDataType StackTop(ST* ps);

//取栈顶元素
STDataType StackTop(ST* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
    return ps->arr[ps->top - 1];
}

那么只要栈不为空，就可以一直取栈顶元素

6. 栈中元素的个数

//获取栈中有效元素个数
int STSize(ST* ps);

//获取栈中有效元素个数
int STSize(ST* ps)
{
    assert(ps);
    return ps->top;
}

总结

栈我们就实现完了，下面是栈实现的完整代码，需要的小伙伴们自取~

//Stack.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{
    STDataType* arr;        //栈数组
    int capacity;           //栈的空间大小
    int top;                //栈顶位置
}ST;
//栈的初始化
void STInit(ST* ps);
//栈的销毁
void StackDestroy(ST* ps);
//数据入栈
void StackPush(ST* ps, STDataType x); //STDataType x 是我们需要插入的数据
//数据出栈
void StackPop(ST* ps);
//取栈顶元素
STDataType StackTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);

//Stack.c
#include"Stack.h"
//栈的初始化
void STInit(ST* ps)
{
    assert(ps);
    ps->arr = NULL;
    ps->capacity = 0;
    ps->top = 0;
}
//栈的销毁
void STDestroy(ST* ps)
{
    assert(ps);
    if(ps->arr)
    free(ps->arr);
    ps->arr = NULL;
    ps->capacity = 0;
    ps->top = 0;
}
//数据入栈
void StackPush(ST* ps, STDataType x)
{
    assert(ps);
    if (ps->capacity == ps->top)           //空间满了需要扩容
    {
        int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;  //三目运算符如果原本栈为空，就赋初始为4个空间，若不为空，则双倍扩容
        STDataType* tem = (STDataType*)realloc(ps->arr, newcapacity * sizeof(ST));
        //判断所开空间是否成功
        if (tem == NULL)
        {
            perror("realloc fail!");
            exit(1);
        }
        ps->arr = tem;
        ps->capacity = newcapacity;
    }
    //入栈开始
    ps->arr[ps->top++] = x;
}
//栈判空
bool StackEmpty(ST* ps)
{
    assert(ps);
    return ps->top == 0;
}
//数据出栈
void StackPop(ST* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
    ps->top--;
}
//取栈顶元素
STDataType StackTop(ST* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
    return ps->arr[ps->top - 1];
}
//获取栈中有效元素个数
int STSize(ST* ps)
{
    assert(ps);
    return ps->top;
}

//测试样例
#include"Stack.h"
void STTest()
{
    ST st;
    STInit(&st);
    //
    StackPush(&st, 1);
    StackPush(&st, 2);
    StackPush(&st, 3);
    StackPush(&st, 4);
    printf("size: %d\n", STSize(&st));//4
    //StackPush(&st, 5);
    //StackPop(&st);
    //循环出栈，直到栈为空
    while (!StackEmpty(&st))
    {
        STDataType data = StackTop(&st);
        printf("%d ", data);
        //出栈
        StackPop(&st);
    }
    printf("size: %d\n", STSize(&st));//0
    ///
    STDestroy(&st);
}
int main()
{
    STTest();
    return 0;
}