本文部分截图来自王道考研

书籍参考:[1]王晓东.数据结构(语言描述)[M].北京:电子工业出版社.2019前言

前言

栈是一种特殊的表,这种表只能在表首进行插入和删除。所以表首对于栈有特殊意义,称为栈顶,表尾称为栈底,不含任何元素的栈称为空栈。可以简单的来说,栈的修改是按后进先出的原则进行,又称为后进先出(Last In First Out)表,简称LIFO表。

假社一个栈SS中的元素为a(n),a(n1),...,a(1)a(n),a(n-1),...,a(1),则称a(1)a(1)为栈底元素,a(n)a(n)为栈顶元素。栈中元素按照a(1),a(2)...,a(n)a(1),a(2)...,a(n)的顺序进栈,第一个进栈的是a(1)a(1),接着依次往后,任何时候,出栈的都是栈顶元素a(n)a(n)。当nn个不同的元素进栈,出栈元素不同排列的个数则为

1n+1C2nn\frac{1}{n+1}C_{2n}^n

这个公式称为卡特兰(Catalan)数

  • InitStack(&S):初始化栈,构造一个空栈SS,分配内存空间。
  • StackFree(&S)`:销毁栈,销毁并释放栈SS所占用的内存空间
  • Push(&S,x):进栈,若栈SS未满,则将xx加入使之成为新栈顶。
  • Pop(&S,&x):出栈,若栈SS非空,则弹出栈顶元素,并用xx返回。
  • StackTop(&S,&x):读入栈顶元素,若栈SS非空,则用xx返回栈顶元素
  • StackEmpty(&S):判断一个栈SS是否为空,若SS为空,则返回True,否则False

栈的顺序存储

栈是一个特殊的表,所以可以使用数组来实现栈,用一个数组data存储栈元素,栈底固定在数组的底部,即data[0]为最早的入栈元素

  • 代码实现
栈的顺序存储实现
// 栈-顺序存储
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

typedef struct astack{
    int top, //栈顶
        maxtop; // 栈空间上界
    int *data; // 存储栈元素的数组
}Astack;

typedef struct astack *Stack; //栈指针类型

Stack StackInit(int size){
    Stack S = (Stack)malloc(sizeof(*S)); // 创建一个空栈
    S->data = (int *)malloc(size*sizeof(int)); //为存储栈元素的数组分配内存空间
    S->maxtop = size; // 栈空间上限为size
    S->top = -1; // 初始化栈顶指针
    return S;
}

void testStack(){
    Stack S;
    S = StackInit(10);
}

int main(){
    testStack();

    return 0;
}

创建一个size大小的栈,因为刚开始的时候,data[0]还没存放数据,所以S->top初始化不能等于00,令它等于1-1

栈顺序存储的基本操作

判断非空

int StackEmpty(Stack S){
    /* 是否为空栈 */
    return S->top < 0; // 如果栈顶小于0,证明还没存储元素
}

进栈操作

void Push(Stack S, int x){
    /* 进栈操作 */
    if (StackFull(S)){
        // 判断是否栈满
        exit(1);
    }
    S->top = S->top+1; // 栈顶加1
    S->data[S->top] = x; // 添加一个元素
}

先判断栈顶指针是否已经达到了栈的最大容量,如果是返回False。因为入栈了一个元素,所以栈顶指针加1,再令当前栈顶指针的位置等于插入元素xx

出栈操作

int Pop(Stack S){
    /* 出栈操作 */
    if(StackEmpty(S)){
        exit(1);
    }
    int x = S->data[S->top]; //返回出栈的元素
    S->top = S->top-1; // 栈顶减一
    return x;
}

令栈顶指针top减去一位,使得逻辑上进行一个出栈操作,但实际数据还是遗留在内存中。

读栈顶元素

int StackTop(Stack S){
    /* 读取栈顶 */
    if (StackEmpty(S)){
        exit(1);
    }
    return S->data[S->top];
}

因为数组是动态分配的,所以需要写一个释放内存的函数

void StackFree(Stack S){
    free(S->data);
    free(S);
}

打印栈

void StackPrint(Stack S){
    /* 打印栈 */
    for (int i=S->top; i>=0; i--){
        // 因为栈后进先出,所以要从栈顶开始打印,一直到栈底
        printf("%d\n",S->data[i]);
    }
}

在同时使用过多个栈的情况,为了不会栈溢出,通常要给栈分配一个较大的栈空间,但是各个栈在算法运行中,所使用的最大空间很难估计。所以可以使用共享栈来提高栈空间的利用率。

例如两个栈使用同一个数组data[0:n],那么利用栈底不变的特性,一个栈底设为0,另一个栈底设为n,分别各自往数组中间延申。这样每一个栈最大的可用空间为n2\frac{n}{2}

栈的链式存储

如果要用到多个栈的时候,可以使用链表作为栈的存储结构,也就是栈的链式存储,就是用指针来实现栈。这样方式使栈有着动态大小,这种实现方式也被称为链栈

  • 代码实现
栈的链式存储实现
// 栈-链式存储
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct snode{ // 栈结构
    int data; // 栈元素
    struct snode *next; // 下一结点指针
}StackNode;

typedef StackNode *SLink; // 栈结点指针类型

typedef struct lstack{ // 栈结构
    SLink top; // 栈顶指针
}Lstack;

typedef Lstack *Stack;

SLink NewStackNode(){
    /* 创建新结点 */
    return (SLink)malloc(sizeof(StackNode));
}

Stack StackInit(){
    /* 初始化栈 */
    Stack S = (Stack)malloc(sizeof(*S));
    S->top = NULL; // top置为空指针
    return S;
}

void testStack(){
    Stack S;
    S = StackInit();
}

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

首先创建一个栈结点的类型,data存储栈元素,next指向下一个结点的指针。使用typedef创建一个snode类型的栈结点指针类型SLink

再创建一个链栈Stack,其中结构只有一个栈顶指针,其指针的类型是栈结点指针类型SLink

栈链式存储的基本操作

判断非空

int StackEmpty(Stack S){
    /* 判断释放为空栈 */
    return S->top == NULL;
}

进栈操作

void Push(Stack S, int x){
    SLink p = NewStackNode(); // 申请一个结点的内存空间
    p->data = x; // 将栈元素存入
    p->next = S->top; // 将新结点的下一个结点指针置空
    S->top = p; // 栈顶结点下一个为p,使p为新的栈顶
}

为新结点申请一块内存空间,同时类型设置为栈结点指针类型,将元素x存入data中,将新结点的下一个结点置为top的下一个结点。因为top的下一个结点是NULL,所以此时结点p的下一个结点也为NULL。这时结点p为栈的栈顶。

出栈操作

int Pop(Stack S){
    /* 出栈操作 */
    if (StackEmpty(S)){
        // 判断栈是否为空栈
        exit(1);
    }
    int x = S->top->data; // 返回出栈元素
    SLink p = S->top; // 另p等于栈顶指针
    S->top = p->next; // 将栈顶指针top,指向p的下一个结点。
    free(p); // 释放p
    return x;
}

假设栈内结点为k>q>s>Nullk->q->s->Null,这时执行出栈操作,这时候的栈顶为ss,定义一个变量xx,另它等于栈顶的data,将出栈元素赋值给x,再函数的结尾处返回。定义一个栈指针类型的结点pp,另它等于栈顶,所以这个时候栈内就变成这样k>q>p>Nullk->q->p->Null。将栈顶指向pp的下一个结点,也就是NullNull,k>q>NULLk->q->NULL,最后将pp占用的结点内存释放。

读栈顶元素

int StackTop(Stack S){
    /* 读取栈顶元素 */
    if (StackEmpty(S)){
        exit(1);
    }
    return S->top->data;
}

打印栈

int StackPrint(Stack S){
    /* 打印栈 */
    if (StackEmpty(S)){
        // 判断非空
        exit(1);
    }
    SLink p = NewStackNode(); // 创建一个结点
    p = S->top; // 令p等于栈顶结点
    while (p!=NULL){
        printf("%d\n",p->data); // 
        p = p->next;
    }
}