数据结构-栈

2341 个字
12 分钟
数据结构-栈
2025-04-18
数据结构
数据结构
/
栈

栈的基本概念#

栈的定义#

栈：是只允许在一端进行插入或删除的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。

img
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。 栈的顺序存储结构可描述为：

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

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

img
img

初始化#

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）时，表示栈已满。

判断栈空#

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

进栈#

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;
}

出栈#

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;
}

读栈顶元素#

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 指针参数）。

完整代码实现#

#include <stdio.h>
#include <stdbool.h>


#define MAXSIZE 5  // 示例栈容量设为5


//栈结构定义
typedef struct SqStack {
    int data[MAXSIZE];
    int top;
} SqStack;


// 初始化栈
void InitStack(SqStack* S) {
    S->top = -1;
}


// 判断栈空
bool StackEmpty(SqStack* S) {
    return (S->top == -1);
}


// 判断栈满
bool StackFull(SqStack* S) {
    return (S->top == MAXSIZE - 1);
}


// 入栈
bool Push(SqStack* S, int x) {
    if (StackFull(S)) {
        printf("栈已满，无法入栈 %d\n", x);
        return false;
    }
    S->top++;
    S->data[S->top] = x;
    printf("入栈元素: %d\n", x);
    return true;
}


// 出栈（通过指针返回栈顶元素）
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;
}


// 获取栈顶元素（通过指针返回）
bool GetTop(SqStack* S, int* x) {
    if (StackEmpty(S)) {
        printf("栈空，无栈顶元素\n");
        return false;
    }
    *x = S->data[S->top];
    printf("当前栈顶元素: %d\n", *x);
    return true;
}


// 打印栈内容（辅助函数）
void PrintStack(SqStack* S) {
    if (StackEmpty(S)) {
        printf("栈空\n");
        return;
    }
    printf("栈内容 (从底到顶): ");
    for (int i = 0; i <= S->top; i++) {
        printf("%d ", S->data[i]);
    }
    printf("\n");
}


int main() {
    SqStack S;
    int val;  // 用于接收出栈/栈顶元素的值


    InitStack(&S);
    PrintStack(&S);  // 栈空


    // 入栈测试
    Push(&S, 10);
    Push(&S, 20);
    Push(&S, 30);
    Push(&S, 40);
    Push(&S, 50);   // 栈满
    Push(&S, 60);   // 触发栈满报错
    PrintStack(&S);  // 10 20 30 40 50


    // 获取栈顶
    GetTop(&S, &val);  // 50


    // 出栈测试
    Pop(&S, &val);     // 50出栈
    Pop(&S, &val);     // 40出栈
    PrintStack(&S);    // 10 20 30


    // 继续出栈直到栈空
    Pop(&S, &val);     // 30
    Pop(&S, &val);     // 20
    Pop(&S, &val);     // 10
    Pop(&S, &val);     // 触发栈空报错
    PrintStack(&S);    // 栈空


    return 0;
}

栈的链式存储结构#

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

img
img

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

链栈的结构定义：#

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

初始化空栈#

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

判断栈空#

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

入栈#

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
  }
}

出栈#

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;
  }
}

取栈顶元素#

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


      }
      return -1;
}

求栈长#

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

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

完整代码实现#

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


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


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


//入栈
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
  }
}


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


//出栈
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;
  }
}


//取栈顶元素
int GetTop_LinkedStack(LinkedStack top)
{
  if(top->next)
      {
            return top->next->data;


      }
      return -1;
}


//主函数
void main()
{
  int i,t,x,a[20];
  LinkedStack top=Init_LinkedStack();//初始化栈
  x=LinkedStack_Empty(top);//判栈空结果赋值给X
  if(x=0)
  {
    printf("栈为空\n");
  }


  printf("请依次输入5个数,开始入栈：\n");
  for(i=0;i<5;i++)
  {
    scanf("%d",&a[i]);
    Push_LinkedStack(top,a[i]);
    x=GetTop_LinkedStack(top);
    if(x!=-1)
    {
      printf("当前栈顶元素为%d\n",x);
    }
  }
  printf("入栈结束\n");
  printf("栈长为%d\n",Length_LinkedStack(top));
  printf("开始出栈:\n");
  for (i=0;i<5;i++)
  {
    Pop_LinkedStack(top,&t);
        printf("%d",t);
  }
  printf("\n");
  printf("出栈后栈长为%d\n",Length_LinkedStack(top));
}

分享到社交平台

将本文分享给你的朋友们

数据结构-栈
https://firefly.cuteleaf.cn/posts/数据结构-栈/
作者
Zhongye
发布于
2025-04-18
版权声明
CC BY-NC-SA 4.0
数据结构-树
数据结构-图
相关文章 智能推荐
1
数据结构-图
数据结构 2025-04-15
2
数据结构-队列
数据结构 2025-04-11
3
数据结构-树
数据结构 2025-04-30
4
数据结构-绪论
数据结构 2025-04-05
5
数据结构复习其一
数据结构 收集到的数据结构复习资料
随机文章 随便看看

评论

留下你的足迹吧~

Profile Image of the Author
Zhongye
南漂中
公告
新的博客站！旧站点传送门 zhongye1.github.io/Arknight-notes
音乐
专辑封面

音乐

暂无播放

0:00 0:00
暂无歌词
分类
标签
站点统计
文章数
142
分类数
14
标签数
214
总字数
339,690
运行天数
0 天
最后更新
0 天前
© 2026 Zhongye. All Rights Reserved. / RSS / Sitemap
Powered by Astro & Firefly

目录