当前位置：首页 > news >正文

【数据结构】栈(stack)

news 2025/7/5 8:05:37

写在前面

本篇文章开始讲解栈的有关知识，其实把顺序表和链表学好，那么这一章便不在话下，栈实际上就是顺序表或链表的一些特殊情况。

用顺序表实现的栈叫做顺序栈

用链表实现的栈叫做链栈

文章的内容分为几个部分，希望读者能快速了解文章的脉络架构：

栈的存储结构——即用结构体定义，包括顺序表栈和链栈

栈的基本操作——入栈和出栈

栈的应用——完整的可执行程序（利用前面的基本操作）

栈的经典力扣题推荐

先识概念

允许插入和删除的一端叫做栈顶(top)，另一端叫做栈底(bottom)

栈和递归联系紧密，可以用栈来模拟递归的实现过程

更多知识，还是翻书为妙、

再看思想

顺序存储结构

#define MAXSIZE 100
#define OK 1
#define ERROR 0typedef int Status;
typedef int ElemType;//顺序栈存储结构
typedef struct
{ElemType data[MAXSIZE];int top;
}SqStack;//进栈
Status Push(SqStack* S, ElemType e)
{//栈满if (S->top == MAXSIZE - 1)return ERROR;S->top++;//将新插入的元素赋值给栈顶S->data[S->top] = e;return OK;
}
/*
1.函数参数接收，一个结构体类型的指针大S，一个int型变量e
2.首先判断那把移动的标尺top(我们将其下标存入其中)是否等于最大值-1，栈满的情况就不能进栈了
3.再把元素的值存入S的数据域之中
*///出栈 
//若栈不空，则删除栈顶元素，用e返回其值
Status Pop(SqStack* S, ElemType* e)
{if (S->top == -1)return ERROR;//将要删除的栈顶元素赋值给e*e = S->data[S->top];//栈顶指针-1S->top--;return OK;
}
/*
1.函数参数接收，一个结构体类型的指针变量大S，一个整型指针类型的变量e
2.我们要出栈，自然栈中得有元素，若没有就结束运行，
3.删除栈顶元素之前，把栈顶结点的数据记录下来，让栈顶计数器top减去1
*/

链栈

//链栈
typedef struct LinkNode
{ElemType data;struct LinkNode* next;
}LinkNode,*LinkStack;//进栈
Status Push(LinkStack* S, ElemType e)
{//创建新结点LinkNode* p = (LinkNode*)malloc(sizeof(LinkNode));p->data= e;p->next = *S;(*S) = p;return OK;
}
/*
1.函数参数接收，链栈指针类型的指针变量大S,整型类型的元素e
2.首先我们创建一个新结点，把它的数据域赋值为e,指针域指向栈顶结点
3.让栈顶指针指向p结点，成为新的栈顶结点
*///出栈——若栈不为空，则删除S的栈顶元素，用e返回其值
Status Pop(LinkStack *S, ElemType* e)
{LinkNode* p;if (S==NULL)return ERROR;*e = (*S)->data;//将栈顶结点赋值给pp = *S;*S = (*S)->next;free(p);return OK;
}/*
1.函数参数接收，链栈类型的指针大S，整型指针e
2.如果是空栈就没有出栈的必要，直接返回0，
3.把结点的数据域赋值给e,用临时指针指向栈顶指针，然后把栈顶指针指向栈顶下面的结点(栈的指针由栈顶指向栈底)
4.之后把临时指针所指向的结点释放即可
*/

再学应用

这是一份可运行的入栈和出栈代码，运用了上面的链栈来实现

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>#define OK 1
#define ERROR 0typedef int Status;
typedef int ElemType;//链栈
typedef struct LinkNode
{ElemType data;struct LinkNode* next;
}LinkNode, *LinkStack;Status InitStack(LinkStack* S)
{*S = NULL;return OK;
}
Status Push(LinkStack* S, ElemType e)
{//创建新结点LinkNode* p = (LinkNode*)malloc(sizeof(LinkNode));p->data = e;p->next = *S;*S = p;return OK;
}Status Pop(LinkStack* S, ElemType* e)
{LinkNode* p;if (*S == NULL)return ERROR;*e = (*S)->data;//将栈顶结点赋值给pp = (*S);*S = (*S)->next;free(p);return OK;
}int main()
{int i = 0;//初始化链栈LinkStack S;ElemType e;InitStack(&S);//进栈printf("请输入5个整数入栈：");for (i = 0; i < 5; i++){scanf("%d", &e);Push(&S, e);}//出栈printf("依次出栈为：");for (i = 0; i < 5; i++){Pop(&S, &e);printf("%d ", e);}return 0;
}