栈——之二

Akari2023-12-292024-03-09

堆栈：

堆栈（Stack）：具有一定操作约束的线性表

只在一端（栈顶，Top）做插入、删除

插入数据：入栈（Push）

删除数据：出栈（Pop）

后入先出：Last In First Out（LIFO）

一、栈的链式存储实现

栈的链式存储结构实际上就是一个单链表，叫做链栈。插入和删除操作只能在链栈的栈顶进行。

/**
 * @brief:
 * @version:
 * @author: @Akari
 * @date: 2023-12-29 21:53:10
 **/

// 栈的链式存储结构实际上就是一个单链表，叫做链栈。插入和删除操作只能在链栈的栈顶进行

#include <stdio.h>
#include <stdlib.h> // 包含 malloc
#include <stdbool.h>

typedef struct SNode{
    int data;
    struct SNode * pNext;
}SNODE, * PSNODE;   // 定义栈节点

typedef struct Stack{
    PSNODE pTop;    // 栈顶
    PSNODE pBottom; // 栈底
}STACK, * PSTACK;   // 定义保存栈节点地址的栈指针

void Init(PSTACK);          // 栈初始化，造出空栈
void Push(PSTACK, int);     // 压栈
void Traverse(PSTACK);      // 遍历栈
bool Pop(PSTACK, int *);    // 出栈
bool IsEmpty(PSTACK) ;      // 栈是否空
void Clear(PSTACK);         // 清除栈


int main(void)  // 栈的链式存储结构
{
    STACK S;
    
    Init(&S);   // 目的是造成一个空栈
    Push(&S, 1);
    Push(&S, 2);
    Push(&S, 3);
    Push(&S, 4);
    Push(&S, 5);
    Traverse(&S);
    
    int val;
    if ( Pop(&S, &val) ){
        printf("出栈成功！出栈的元素是：%d\n", val);
    }
    else{
        printf("出栈失败！\n");
    }
    Traverse(&S);
    
    Clear(&S);
    Traverse(&S);
    
    return 0;
}


void Init(PSTACK pS){
    pS->pTop = (PSNODE)malloc(sizeof(SNODE));   // 新建栈节点：头栈节点
    if ( NULL == pS->pTop ){
        printf("动态内存分配失败！\n");
        exit(-1);
    }
    
    pS->pBottom = pS->pTop;     // 栈顶和栈底都指向指针域为空的头栈节点
    pS->pTop->pNext = NULL;     // 等价于：pS->pBottom->pNext = NULL; 头栈节点的指针域为 NULL
}

void Push(PSTACK pS, int val){
    PSNODE pNew = (PSNODE)malloc(sizeof(SNODE));
    pNew->data = val;   // 给栈节点中的数据赋值
    pNew->pNext = pS->pTop; // pS->Top 不能改成pS->pBpttom
                            // 栈节点的指针域保存下一个节点的地址
    pS->pTop = pNew;    // 更新栈顶：新的栈节点变成新的栈顶
}

void Traverse(PSTACK pS){
    PSNODE p = pS->pTop;    // 临时节点指向栈顶
    
    while ( p != pS->pBottom ){     // 是否遍历到栈底
        printf("%d ", p->data);
        p = p->pNext;
    }
    printf("\n");
}

bool IsEmpty(PSTACK pS){
    if ( pS->pTop == pS->pBottom )
        return true;
    else
        return false;
}

/*
  把pS所指向的栈顶出栈一次
  并把出栈的元素存入 pVal 形参所指向的变量中
  出栈失败返回 false，否则返回 true
 */
bool Pop(PSTACK pS, int * pVal){
    if ( IsEmpty(pS) ){
        printf("栈为空！\n");
        return false;
    }
    
    PSNODE r = pS->pTop;    // 临时节点指向栈顶
    *pVal = r->data;        // 保存数据
    pS->pTop = r->pNext;    // 更新栈顶
                            // 等价于：pS->pTop = pS->Top->pNext;
    free(r);
    r = NULL;
    
    return true;
}

void Clear(PSTACK pS){
    if ( IsEmpty(pS) ){
        return;
    }
    
    PSNODE r = pS->pTop;    // r 指向栈顶
    PSNODE q = NULL;        // q 临时保存栈节点的地址
    while ( r != pS->pBottom ){ // 是否遍历到栈底
        q = r->pNext;   // 栈节点的指针域（下一节点地址）临时保存在 q 中
        free(r);
        r = q;          // q 中的下一节点地址赋给 r ，准备循环释放下一节点内存
    }
    pS->pTop = pS->pBottom; // 栈顶和栈底都指向指针域为空的头栈节点
}

二、栈的顺序存储实现

栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组。

/**
 * @brief:
 * @version:
 * @author: @Akari
 * @date: 2024-01-01 20:59:56
 **/

// 栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成

#include <stdio.h>
#include <stdbool.h>
#define MaxSize 20      // 存储空间初始分配量

typedef struct SNode{
    int data[MaxSize];  // 存储堆栈元素
    int Top;    // 记录栈顶元素下标 / 用于栈顶指针
}STACK;

void Init(STACK *);         // 栈初始化，造出空栈
bool Push(STACK *, int);    // 压栈
void Traverse(STACK *);     // 遍历栈
bool Pop(STACK *, int *);   // 出栈
bool IsEmpty(STACK *) ; // 栈是否空
bool IsFull(STACK *);       // 栈是否满
void Clear(STACK *);        // 清除栈


int main(void)
{
    STACK s;
    
    Init(&s);
    Push(&s, 1);
    Push(&s, 2);
    Push(&s, 3);
    Push(&s, 4);
    Push(&s, 5);
    Traverse(&s);
    
    int val;
    if ( Pop(&s, &val) ){
        printf("出栈成功！出栈的元素是：%d\n", val);
    }
    else{
        printf("出栈失败！\n");
    }
    Traverse(&s);
    
    Clear(&s);
    Traverse(&s);
    
    return 0;
}


void Init(STACK *s){
    s->Top = -1;
    return;
}

bool Push(STACK *s, int val){
    if ( IsFull(s) ){
        printf("栈已满！\n");
        return false;
    }
    else{
        s->Top++;
        s->data[s->Top] = val;
        return true;
    }
}

void Traverse(STACK *s){
    if ( IsEmpty(s) ){
        printf("栈为空！\n");
        return;
    }
    
    for ( int i = 0; i <= s->Top; i++ ){    // Top 为栈顶元素，即数组下标所以是 <=
        printf("%d ", s->data[i]);
    }
    printf("\n");
    
    return;
}

bool Pop(STACK *s, int *pVal){
    if ( IsEmpty(s) ){
        printf("栈为空！\n");
        return false;
    }
    else{
        *pVal = s->data[s->Top];
        s->Top--;
        return true;
    }
}

bool IsEmpty(STACK *s){
    if ( -1 == s->Top ){
        return true;
    }
    else
        return false;
}

bool IsFull(STACK *s){
    if ( MaxSize - 1 == s->Top ){
        return true;
    }
    else
        return false;
}

void Clear(STACK *s){
    s->Top = -1;
    return;
}

1、函数的形参`STACK *s`

每个函数中形参都是STACK *s，有必要都用指针吗？因为这是以数组实现的栈

函数参数使用 STACK *s，即指向 STACK 结构体的指针。这是因为在 C 语言中，函数参数传递通常是通过值传递的——如果传递一个结构体，那么会复制整个结构体的内容，这可能引起性能上的开销。

虽然静态栈是基于数组实现的，而数组本身已经是一个指针，但传递 STACK *s 还是有好处的，因为可能需要在函数中修改 Top 指针，而不是只修改数组的内容。

2、指针的优劣

指针的好处：

内存效率：
通过传递指针，避免了在函数调用时复制整个结构体的开销，尤其是当结构体很大时。

原地修改：
通过指针，可以在函数内部修改原始结构体，而不是修改传递给函数的副本。这对于栈这种需要修改状态的数据结构来说是很重要的。

一致性：
当使用指针传递结构体时，对结构体的修改会直接反映到调用者的结构体上，这有助于保持一致性。