从零开始学数据结构与算法（二） ： 栈

一、栈的逻辑结构

1.栈的定义

栈(stack)是限定在表的一端进行插入和删除的线性表，允许插入和删除的一段叫做栈顶，另外一段称为栈底，不含任何数据元素的栈称为空栈。

任何时刻出栈的元素都只能是栈顶元素，即最后入栈者最先出栈，所以栈中元素除了线性关系外，还具有后进后出的特性。

栈的示意图：

2.栈的抽象数据类型定义

虽然对插入和删除操作的位置限制减少了栈操作的灵活性，但也同时使得栈的操作更有效更容易的实现。其抽象数据类型定义为：

ADT Stack
DataModel
    栈中元素具有后进后出特性，相邻元素具有前驱和后继关系
Opertion
    InitStack
        输入：无
        功能：栈的初始化
        输出：一个空栈
    DestroyStack
        输入：无
        功能：栈的销毁
        输出：释放栈的存储空间
    Push
        输入：数据元素x
        功能：入栈操作，在栈顶插入一个元素x
        输出：如果插入成功，栈顶增加一个元素，否则，返回插入失败的信息
    Pop
        输入：无
        功能：出栈操作，删除栈顶元素
        输出：如果删除成功，返回被删除的元素，否则返回删除失败的信息
    GetTop
        输入：无
        功能：取栈顶元素值，读取当前的栈顶元素
        输出：若栈不空，返回当前的栈顶元素值，否则返回取栈顶失败的信息
    Empty
        输入：无
        功能：判空操作，判断栈是否为空
        输出：如果栈为空，返回1，否则返回0
endADT

二、 栈的顺序存储结构及实现

1.顺序栈的顺序存储结构定义

栈的顺序结构被称为顺序栈(sequential stack)。
顺序栈（Sequential Stack）是一种基于数组实现的栈数据结构。它遵循后进先出（Last In, First Out，LIFO）的原则，即最后进入栈的元素首先被访问或移除。

顺序栈的特点和操作如下：

1. 存储结构：顺序栈使用一段连续的内存空间（通常是数组）来存储栈中的元素。栈的大小由数组的长度决定。

2. 栈顶指针：顺序栈维护一个栈顶指针，指向栈顶元素的位置。初始时，栈顶指针可以被设置为 -1，表示栈为空。

3. 入栈（Push）：将元素压入栈顶。入栈操作需要执行以下步骤：

4. 检查栈是否已满（栈顶指针是否达到数组的最大容量）。

5. 若栈未满，则将栈顶指针加一，并将元素存储在栈顶位置。

6. 出栈（Pop）：从栈顶删除元素并返回。出栈操作需要执行以下步骤：

7. 检查栈是否为空（栈顶指针是否为 -1）。

8. 若栈非空，则取出栈顶元素并将栈顶指针减一。

9. 获取栈顶元素（Top）：返回栈顶位置的元素，但不进行删除操作。需要先检查栈是否为空。

10. 判空（IsEmpty）：检查栈是否为空，即栈顶指针是否为 -1。

11. 判满（IsFull）：检查栈是否已满，即栈顶指针是否达到数组的最大容量。

顺序栈的优点是操作简单、效率高，特别适用于已知栈的最大容量的情况。由于使用数组实现，内存空间是连续的，因此顺序栈的内存分配相对简单。

然而，顺序栈的缺点是容量固定，一旦达到最大容量，无法动态扩展。如果需要处理动态变化的数据集合，可以考虑使用链式栈（链表实现）。

总结起来，顺序栈是一种简单且常用的栈实现方式，适用于已知容量且不需要频繁扩展的场景。
下面给出顺序栈的存储结构定义：

#define StackSize 100 //假设栈元素最多有100个

typedef int DataType; //定义栈中数据元素，假设是int

typedef struct
{
    DataType data[StackSize]; //存放栈元素的数组
    int top;//栈顶元素的下标
}SeqStack;

2.顺序栈的实现

· 顺序栈的初始化

初始化一个空的顺序栈只需要将栈顶位置top置为-1，代码实现如下：

void InitStack(SeqStack * S)
{
    S->top = -1;
}

·顺序栈的销毁

顺序栈是静态存储分配，在顺序栈变量退出作用域是自动释放顺序栈所占存储单元，因此顺序栈无须销毁。

·入栈操作

在栈中插入一个元素只需要将top加1，然后再top位置上填入插入新元素x，函数Push的返回值表示插入是否成功，算法代码实现如下：

int Push(SeqStack* S, int x)
{
    if (S->top == StackSize - 1)
    {
        printf("上溢错误，插入失败\n");
        return 0;
    }
    S->data[++S->top] = x;
    return 1;
}

·出栈操作

出栈操作只需要取出栈顶元素，然后将栈顶位置top减1。如果出栈成功，返回1，否则返回0，代码如下：

int Pop(SeqStack * S, DataType * ptr)
{
    if (S->top == -1)
    {
        printf("下溢错误，删除失败\n");
        return 0;
    }
    *ptr = S->data[S->top--];
    return 1;
}

·取栈顶元素

取栈顶元素只是将top位置的栈顶元素取出，不修改栈顶位置。代码如下：

int GetTop(SeqStack* S, DataType* ptr)
{
    if (S->top == -1)
    {
        printf("下溢错误，取栈顶失败\n");
        return 0;
    }
    *ptr = S->data[S->top];
    return 1;
}

·判空操作

顺序栈的判空操作只需判断top是否等于-1，代码实现如下：

int Empty(SeqStack* S)
{
    if (S->top == -1) return 1;
    return 0;
}

3.顺序表的使用

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

//将上述顺序表的存储结构定义和功能放到此处

int main() {
    SeqStack stack;
    InitStack(&stack);

    printf("Testing Push:\n");
    for (int i = 1; i <= 5; i++) {
        if (Push(&stack, i)) {
            printf("%d pushed to the stack.\n", i);
        }
    }

    printf("\nTesting Pop:\n");
    while (!Empty(&stack)) {
        DataType data;
        if (Pop(&stack, &data)) {
            printf("%d popped from the stack.\n", data);
        }
    }

    printf("\nTesting GetTop:\n");
    Push(&stack, 10);
    Push(&stack, 20);
    Push(&stack, 30);
    DataType top;
    if (GetTop(&stack, &top)) {
        printf("Top element: %d\n", top);
    }

    return 0;
}

三、栈的链式存储结构及实现

1.链栈的存储结构定义

栈的链式存储结构称为链栈(linked stack)，通常用单链表来表示，其结点结构与单链表的结点结构相同。因为只在栈顶执行插入操作和删除操作，显然用单链表的头做栈顶是最方便的，通常将链栈表示为下图的形式。

这里给出链栈，也就是单链表的存储结构定义：

typedef int DataType; // 定义栈元素中的数据类型，假设是int

typedef struct
{
    DataType data;
    Node* next;
}Node;

2.链栈的实现

链栈基本操作的本质是单链表操作的简化，由于插入删除操作只能在单链表的头部进行，因此算法时间复杂度均为O(1)。

·链栈的初始化

空链表中只有头结点，代码如下：

Node* InitStack()
{
    Node* top = (Node*)malloc(sizeof Node);
    top->next = NULL;
    return top;
}

·链栈的销毁

链栈是动态存储分配，在链栈变量退出作用域前要释放链栈的存储空间，代码如下：

void DestroyStack(Node* top)
{
    Node* p = top;
    while (top != NULL)
    {
        top = top->next;
        free(p);
        p = top;
    }
}

·入栈操作

链栈的插入只用考虑栈顶插入，代码如下：

void Push(Node* top, DataType x)
{
    Node* s = (Node*)malloc(sizeof Node);
    s->data = x;
    s->next = top->next;
    top->next = s;
}

·出栈操作

链栈的出栈操作同样只用考虑栈顶，函数Pop的返回值表示出栈操作是否正确执行，如果出栈正确返回1，否则返回0，代码如下：

int Pop(Node* top, DataType* ptr)
{
    Node* p = top->next;
    if (top->next == NULL)
    {
        printf("下溢错误，删除失败\n");
        return 0;
    }
    *ptr = p->data;
    top->next = p->next;
    free(p);
    return 1;
}

·取栈顶元素

取栈顶元素只需要返回链表top所指结点的数据域即可，代码如下：

int GetTop(Node* top, DataType *ptr)
{
    if (top == NULL)
    {
        printf("下溢错误，取栈顶失败\n");
        return 0;
    }
    *ptr = top->data; 
    return 1;
}

·判空操作

int Empty(Node* top)
{
    if(top == NULL) return 1;
    return 0;
}

3.链栈的使用

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h> 

typedef int DataType; // 定义栈元素中的数据类型，假设是int

typedef struct Node
{
    DataType data;
    struct Node* next;
}Node;

//上述功能实现放在此处

int main()
{
    DataType x;
    Node* top = NULL;
    top = InitStack();
    printf("对15和10执行入栈操作，");
    Push(top, 15);
    Push(top, 10);
    if (GetTop(top, &x) == 1)
        printf("当前栈顶元素为：%d\n", x);
    if(Pop(top,&x) == 1)
        printf("执行一次出栈操作，删除元素：%d\n", x);
    if (GetTop(top, &x) == 1)
        printf("当前栈顶元素为：%d\n", x);
    if (Empty(top) == 0)
    {
        printf("栈不为空\n");
    }
    else
    {
        printf("栈为空\n");
    }
    if (Pop(top, &x) == 1)
        printf("执行一次出栈操作，删除元素：%d\n", x);
    if (Empty(top) == 0)
    {
        printf("栈不为空\n");
    }
    else
    {
        printf("栈为空\n");
    }
}

四、顺序栈链栈的比较

顺序栈和链栈的基本算法时间复杂度均为O(1),因此唯一可以比较的是空间性能。初始时顺序栈必须确定一个固定的长度，所以有存储元素个数的限制和浪费空间的问题。链栈没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。所以当栈使用过程中元素个数变化较大时，应该采用链栈，反之，应该采用顺序栈。