JavaScript is required

数据结构-栈

算法#数据结构#栈

栈的基本概念

栈的定义

栈：是只允许在一端进行插入或删除的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。 img栈顶（Top）：线性表允许进行插入删除的那一端。 栈底（Bottom)：固定的，不允许进行插入和删除的另一端。 空栈：不含任何元素的空表。

栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构

栈的常见基本操作

InitStack(&S)：初始化一个空栈S

StackEmpty(S)：判断一个栈是否为空，若栈为空则返回true，否则返回false

Push(&S, x)：进栈（栈的插入操作），若栈S未满，则将x加入使之成为新栈顶

Pop(&S, &x)：出栈（栈的删除操作），若栈S非空，则弹出栈顶元素，并用x返回

GetTop(S, &x)：读栈顶元素，若栈S非空，则用x返回栈顶元素

DestroyStack(&S)：栈销毁，并释放S占用的存储空间（“&”表示引用调用）

栈的顺序存储结构

栈的顺序存储

采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素的位置。 若存储栈的长度为MAXSIZE，则栈顶位置top必须小于MAXSIZE。当栈存在一个元素时，top等于0，因此通常把空栈的判断条件定位top等于-1。 栈的顺序存储结构可描述为：

c
#define MAXSIZE 5
//定义栈中元素的最大个数
typedef struct SqStack{
    int data[MAXSIZE];
    int top;
}SqStack;

若现在有一个栈，MAXSIZE是5，则栈的普通情况、空栈、满栈的情况分别如下图所示：

img

初始化

c
void InitStack(SqStack* S){
    //SqStack& S 是 C++ 的引用参数，用于直接修改外部栈对象
    //若用 C 语言，需改用指针（SqStack* S）
    S->top = -1;             //初始化栈顶指针
}

为什么要用 S->top = -1？

顺序栈的本质是一个数组，栈顶指针 top 表示当前栈顶元素在数组中的位置索引。 初始化时 top = -1 有

空栈条件：top == -1 当栈中没有元素时，top 指向数组的“前一个位置”（即无效索引），逻辑上表示“无元素”。

入栈操作

先让 top++，移动到下一个可用位置；将新元素存入 data[top]。 例如，第一次入栈时，top 从 -1 变为 0，元素存入 data[0]，对应数组的第一个索引。

判断栈满

栈满条件：top == MAX_SIZE - 1 如果数组大小为 MAX_SIZE，当 top 指向最后一个位置（即 MAX_SIZE - 1）时，表示栈已满。

判断栈空

c
bool StackEmpty(SqStack* S){
    if( S->top == -1){
        return true;
        //栈中没有元素时，`top` 指向数组的“前一个位置”（即无效索引），逻辑上表示“无元素”
    }
    return false;
}

进栈

c
bool Push(SqStack* S, int x){
    if( S->top == MAXSIZE - 1 ){ //栈满，报错
        return false;
    }
    S->top++ ;                  //栈顶指针加1
    S->data[S->top] = x;         //入栈,写入元素到新栈顶位置
    //S->data[S->top]代表栈顶元素
    return true;
}

出栈

c
bool Pop(SqStack* S, int* x) {//通过指针修改外部变量
    if (StackEmpty(S)) {
        printf("栈空，无法出栈\n");
        return false;
    }
    *x = S->data[S->top];
    S->top--;
    printf("出栈元素: %d\n", *x);
    return x;
}

读栈顶元素

c
bool GetTop(SqStack* S, int* x) {//通过指针修改外部变量
    if (StackEmpty(S)) {
        printf("栈空，无栈顶元素\n");
        return false;
    }
    *x = S->data[S->top];
    printf("当前栈顶元素: %d\n", *x);
    return true;
}

出栈和读栈顶元素操作需要返回两个信息：

  • 是否成功（通过 bool 返回值）。
  • 得到的元素值（通过 int* x 指针参数）。

完整代码实现

栈的链式存储结构

采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头节点，Lhead指向栈顶元素

img

对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top=NULL的时候。

链栈的结构定义：

c
// 定义链式栈的节点结构体
typedef struct LinkedStackNode
{
    int data;                       // 存储栈元素
    struct LinkedStackNode * next;  // 指向下一节点的指针
} LinkedStackNode, * LinkedStack;   // 类型别名：LinkedStackNode表示节点，LinkedStack表示节点指针
LinkedStack top; // 声明一个栈顶指针（本质是LinkedStackNode*类型）

初始化空栈

c
//初始化
LinkedStack Init_LinkedStack()
{
    LinkedStack top=(LinkedStackNode * )malloc (sizeof( LinkedStackNode));
    if(top!=NULL)//申请空间成功
    top->next=NULL;//设置栈顶指针为空
    return top;
}

判断栈空

c
//判栈空
int LinkedStack_Empty(LinkedStack top)
{
    if(top->next==NULL)//检查栈顶指针的值
    {
        return 1;//栈S为空，函数返回1
    }
    else
    {
        return 0;
    }
}

入栈

c
int Push_LinkedStack(LinkedStack top,elemtype x)
    //插入数据元素x为新的栈顶元素
{
    LinkedStackNode * node;
    node=(LinkedStackNode * )malloc(sizeof(LinkedStackNode));
    if(node==NULL)
    {
        return 0;//申请结点空间失败,插入失败，函数返回0
    }
    else
    {
        node->data=x;//设置新结点的数据域
        node->next=top->next;//设置新结点的指针城
        top->next=node;//设置头结点指针城指向新的栈顶元素
        return 1;//插入成功，函数返回1
    }
}

出栈

c
int Pop_LinkedStack(LinkedStack top, elemtype *x)
{   LinkedStackNode * node;
    if(top->next==NULL)
    {
        return 0;
    }
    else
    {
        node=top->next;//将原栈顶数据元素弹出并赋给node
        *x=node->data;//将原栈顶数据元素的数据赋值给x
        top->next=node->next;//top指向链栈中的下一个数据元素
        free (node);//释放原栈顶数据元素所占的空间
        return 1;
    }
}

取栈顶元素

c
int GetTop_LinkedStack(LinkedStack top)
{
    if(top->next)
      {
            return top->next->data;

      }
      return -1;
}

求栈长

设置计数器，随top指针后移，计数器加1，直到遍历完所有元素。

c
//求栈长
int Length_LinkedStack(LinkedStack top)
{
    int count = 0;
    while(top->next!=NULL)
    {
        ++count;
        top=top->next;
    }
    return count;
}

完整代码实现