栈（Stack）的原理与代码实现
栈（stack）
原理说明：
学习数据结构的目的是为了更好的处理和存储数据，对于顺序表而言改查比较容易，增删比较麻烦，对于链式表而言，增删比较简单，改查比较麻烦，所以每种数据结构都有不同的特点，用户需要选择合适的数据结构。
栈内存自顶向下进行递增，其实栈和顺序表以及链式表都一样，都属于线性结构，****存储的数据的逻辑关系也是一对一的。
如上图所示，栈的模型类似一一个瓶子。
1）栈的一端是封闭的，数据的插入与删除只能在栈的另一端进行，也就是栈遵循“*后进先出*”的原则。也被成为“LIFO”结构，意思是“last input first output”。
2）栈（stack）,存储货物或供旅客住宿的地方,可引申为仓库、中转站，所以引入到计算机领域里，就是指数据暂时存储的地方，所以才有进栈（PUSH）、出栈（POP）的说法。
栈原理举例
如图所示，在三本书均放进“栈”中后，我们想要取得Blue书时，必须将前两本书依次取出，即是栈“先进后出”特点的展示。
闭合的一端被称为栈底（Stack Bottom），允许数据的插入与删除的一端被称为栈顶（Stack Top），不包含任何元素的栈被称为空栈。
- 把数据插入到栈空间的动作被称为入栈或者压栈（push）
- 从栈空间中删除数据的动作被称为出栈或者弹栈（pop）
代码实现
由于栈也是一种线性结构，所以可以以数组或者链表作为基础，在此基础上实现栈的操作。
顺序栈：以数组作为基础实现栈空间
数组在内存中占用一块连续的空间，也就是数组元素的内存地址是连续的。为了实现栈，一般是把数组头作为栈底，数组头部到数组尾部作为栈的增长方向，也就是用户只在数组尾部对数据进行插入和删除。这样规定的原因其一是因为数组能够进行随机访问，所以数组的尾插较为便利。
代码实现：
为了方便管理顺序栈所以需要构造管理顺序栈信息的结构体类型，用于记录重要参数，如下：
//指的是顺序栈中的元素的数据类型，用户可以根据需要进行修改
typedef int DataType_t;
//构造记录顺序栈SequenceStack各项参数(栈底地址+栈容量+栈顶元素的下标)的结构体
typedef struct SequenceStack
{
DataType_t * Bottom; //记录栈底地址
unsigned int Size; //记录栈容量
int Top; //记录栈顶元素的下标
}SeqStack_t;
-
创建一个空的顺序栈，并为记录顺序栈信息的结构体申请堆内存，并进行初始化即可
/********************************************************************* * * name : SeqStack_Create * function : 创建一个空的顺序栈，并为记录顺序栈信息的结构体 申请堆内存，并进行初始化即可！ * argument : * @size :栈的容量大小 * * retval : 调用成功返回顺序栈的地址 * author : [email protected] * date : 2024/04/25 * note : none * * *****************************************************************/ //创建顺序表并对顺序栈进行初始化 SeqStack_t * SeqStack_Create(unsigned int size) { //1.利用calloc为顺序栈的管理结构体申请一块堆内存 SeqStack_t *Manager = (SeqStack_t *)calloc(1,sizeof(SeqStack_t)); if(NULL == Manager) { perror("calloc memory for manager is failed"); exit(-1); //程序异常终止 } //2.利用calloc为所有元素申请堆内存 Manager->Bottom = (DataType_t *)calloc(size,sizeof(DataType_t)); if (NULL == Manager->Bottom) { perror("calloc memory for Stack is failed"); free(Manager); exit(-1); //程序异常终止 } //3.对管理顺序栈的结构体进行初始化（元素容量 + 最后元素下标） Manager->Size = size; //对顺序栈中的容量进行初始化 Manager->Top = -1; //由于顺序栈为空，则栈顶元素的下标初值为-1 return Manager; } -
根据栈的特性，把新元素从栈顶入栈，也就是从数组的尾部进行元素插入，操作如下：
/********************************************************************* * * name : SeqStack_IsFull * function : 判断顺序栈是否已满 * argument : * @Manager :顺序栈的地址 * * retval : 调用成功返回bool型，满了则返回true，没满返回false * author : [email protected] * date : 2024/04/25 * note : none * * *****************************************************************/ bool SeqStack_IsFull(SeqStack_t *Manager) { return (Manager->Top + 1 == Manager->Size) ? true : false; } /********************************************************************* * * name : SeqStack_Push * function : 根据栈的特性，把新元素从栈顶入栈，也就是从数组的尾部进行元素插入 * argument : * @Manager :顺序栈的地址 @Date :要入栈的数据 * * retval : 调用成功返回bool型，满了则返回true，没满返回false * author : [email protected] * date : 2024/04/25 * note : none * * *****************************************************************/ //入栈 bool SeqStack_Push(SeqStack_t *Manager, DataType_t Data) { //1.判断顺序栈是否已满 if ( SeqStack_IsFull(Manager) ) { printf("SeqStack Full is Full!\n"); return false; } //2.如果顺序栈有空闲空间，则把新元素添加到顺序栈的栈顶 Manager->Bottom[++Manager->Top] = Data; return true; } -
根据栈的特性，把元素从栈顶出栈，也就是把元素从数组的尾部把元素删除
/********************************************************************* * * name : SeqStack_IsEmpty * function : 判断顺序栈是否为空 * argument : * @Manager :顺序栈的地址 * * retval : 调用成功返回bool型，空了则返回true，没空返回false * author : [email protected] * date : 2024/04/25 * note : none * * *****************************************************************/ bool SeqStack_IsEmpty(SeqStack_t *Manager) { return (-1 == Manager->Top) ? true : false; } /********************************************************************* * * name : SeqStack_Pop * function : 根据栈的特性，把元素从栈顶出栈，也就是把元素从数组的尾部把元素删除 * argument : * @Manager :顺序栈的地址 * * retval : 调用成功返回新的栈地址 * author : [email protected] * date : 2024/04/25 * note : none * * *****************************************************************/ //出栈 DataType_t SeqStack_Pop(SeqStack_t *Manager) { DataType_t temp = 0; //用于存储出栈元素的值 //1.判断顺序栈是否为空 if ( SeqStack_IsEmpty(Manager) ) { printf("SeqStack is Empty!\n"); return; } //2.由于删除了一个元素，则需要让顺序栈的栈顶元素下标-1 temp = Manager->Bottom[Manager->Top--]; return temp; } -
对顺序栈中的元素进行遍历，只需要从顺序栈的栈底开始向栈顶进行遍历
//遍历顺序表的元素 void SeqStack_Print(SeqStack_t *Manager) { for (int i = 0; i <= Manager->Top; ++i) { printf(" Stack Element[%d] = %d\n",i,Manager->Bottom[i]); } }代码完整展示
/******************************************************************* * * file name: SequenceStack.c * author : [email protected] * date : 2024/04/25 * function : 该案例是以数组作为基础实现栈空间，并且把数组头作为栈底， 数据头部到数据尾部作为栈的增长方向。 * note : None * * CopyRight (c) 2023-2024 [email protected] All Right Reseverd * * *****************************************************************/ #include <stdio.h> #include <stdbool.h> #include <stdlib.h> //指的是顺序栈中的元素的数据类型，用户可以根据需要进行修改 typedef int DataType_t; //构造记录顺序栈SequenceStack各项参数(栈底地址+栈容量+栈顶元素的下标)的结构体 typedef struct SequenceStack { DataType_t * Bottom; //记录栈底地址 unsigned int Size; //记录栈容量 int Top; //记录栈顶元素的下标 }SeqStack_t; /********************************************************************* * * name : SeqStack_Create * function : 创建一个空的顺序栈，并为记录顺序栈信息的结构体 申请堆内存，并进行初始化即可！ * argument : * @size :栈的容量大小 * * retval : 调用成功返回顺序栈的地址 * author : [email protected] * date : 2024/04/25 * note : none * * *****************************************************************/ //创建顺序表并对顺序栈进行初始化 SeqStack_t * SeqStack_Create(unsigned int size) { //1.利用calloc为顺序栈的管理结构体申请一块堆内存 SeqStack_t *Manager = (SeqStack_t *)calloc(1,sizeof(SeqStack_t)); if(NULL == Manager) { perror("calloc memory for manager is failed"); exit(-1); //程序异常终止 } //2.利用calloc为所有元素申请堆内存 Manager->Bottom = (DataType_t *)calloc(size,sizeof(DataType_t)); if (NULL == Manager->Bottom) { perror("calloc memory for Stack is failed"); free(Manager); exit(-1); //程序异常终止 } //3.对管理顺序栈的结构体进行初始化（元素容量 + 最后元素下标） Manager->Size = size; //对顺序栈中的容量进行初始化 Manager->Top = -1; //由于顺序栈为空，则栈顶元素的下标初值为-1 return Manager; } /********************************************************************* * * name : SeqStack_IsFull * function : 判断顺序栈是否已满 * argument : * @Manager :顺序栈的地址 * * retval : 调用成功返回bool型，满了则返回true，没满返回false * author : [email protected] * date : 2024/04/25 * note : none * * *****************************************************************/ bool SeqStack_IsFull(SeqStack_t *Manager) { return (Manager->Top + 1 == Manager->Size) ? true : false; } /********************************************************************* * * name : SeqStack_Push * function : 根据栈的特性，把新元素从栈顶入栈，也就是从数组的尾部进行元素插入 * argument : * @Manager :顺序栈的地址 @Date :要入栈的数据 * * retval : 调用成功返回bool型，满了则返回true，没满返回false * author : [email protected] * date : 2024/04/25 * note : none * * *****************************************************************/ //入栈 bool SeqStack_Push(SeqStack_t *Manager, DataType_t Data) { //1.判断顺序栈是否已满 if ( SeqStack_IsFull(Manager) ) { printf("SeqStack Full is Full!\n"); return false; } //2.如果顺序栈有空闲空间，则把新元素添加到顺序栈的栈顶 Manager->Bottom[++Manager->Top] = Data; return true; } /********************************************************************* * * name : SeqStack_IsEmpty * function : 判断顺序栈是否为空 * argument : * @Manager :顺序栈的地址 * * retval : 调用成功返回bool型，空了则返回true，没空返回false * author : [email protected] * date : 2024/04/25 * note : none * * *****************************************************************/ bool SeqStack_IsEmpty(SeqStack_t *Manager) { return (-1 == Manager->Top) ? true : false; } /********************************************************************* * * name : SeqStack_Pop * function : 根据栈的特性，把元素从栈顶出栈，也就是把元素从数组的尾部把元素删除 * argument : * @Manager :顺序栈的地址 * * retval : 调用成功返回新的栈地址 * author : [email protected] * date : 2024/04/25 * note : none * * *****************************************************************/ //出栈 DataType_t SeqStack_Pop(SeqStack_t *Manager) { DataType_t temp = 0; //用于存储出栈元素的值 //1.判断顺序栈是否为空 if ( SeqStack_IsEmpty(Manager) ) { printf("SeqStack is Empty!\n"); return; } //2.由于删除了一个元素，则需要让顺序栈的栈顶元素下标-1 temp = Manager->Bottom[Manager->Top--]; return temp; } /********************************************************************* * * name : SeqStack_Push * function : 对顺序栈中的元素进行遍历，只需要从顺序栈的栈底开始向栈顶进行遍历 * argument : * @Manager :顺序栈的地址 * * retval : 调用成功返回bool型，满了则返回true，没满返回false * author : [email protected] * date : 2024/04/25 * note : none * * *****************************************************************/ //遍历顺序表的元素 void SeqStack_Print(SeqStack_t *Manager) { for (int i = 0; i <= Manager->Top; ++i) { printf(" Stack Element[%d] = %d\n",i,Manager->Bottom[i]); } } int main(int argc, char const *argv[]) { //创建一个容量大小为10的栈 SeqStack_t *SequenceStack = SeqStack_Create(10); //入栈 //1.没满时 SeqStack_Push(SequenceStack, 10); SeqStack_Push(SequenceStack, 20); SeqStack_Push(SequenceStack, 30); SeqStack_Push(SequenceStack, 40); SeqStack_Push(SequenceStack, 50); SeqStack_Push(SequenceStack, 60); SeqStack_Push(SequenceStack, 70); SeqStack_Push(SequenceStack, 80); SeqStack_Push(SequenceStack, 90); SeqStack_Push(SequenceStack, 100); printf("\n"); //遍历显示 SeqStack_Print(SequenceStack); printf("\n"); //2.满时进栈 SeqStack_Push(SequenceStack, 666); printf("\n"); //遍历显示 SeqStack_Print(SequenceStack); printf("\n"); //出栈 //1.有元素时出栈 SeqStack_Pop(SequenceStack); SeqStack_Pop(SequenceStack); SeqStack_Pop(SequenceStack); SeqStack_Pop(SequenceStack); SeqStack_Pop(SequenceStack); SeqStack_Pop(SequenceStack); SeqStack_Pop(SequenceStack); printf("\n"); //遍历显示 SeqStack_Print(SequenceStack); printf("\n"); SeqStack_Pop(SequenceStack); SeqStack_Pop(SequenceStack); SeqStack_Pop(SequenceStack); printf("\n"); //遍历显示 SeqStack_Print(SequenceStack); printf("\n"); //2.空时出栈 SeqStack_Pop(SequenceStack); return 0; }结果验证：
链式栈：以链表作为基础实现栈空间
如果打算实现链式栈，一般是以链表作为基础，一般是把链表头部作为栈顶，方便数据的插入和删除（头插+头删），链式栈相当于是一个单向不循环的链表。
为了方便管理链式栈，所以需要构造链式栈的结构体类型，如下：
//指的是链式栈中的元素的数据类型，用户可以根据需要进行修改
typedef int DataType_t;
//构造记录链式栈各项参数(栈中存储数据 + 栈顶元素的地址)的结构体
typedef struct ChainStack
{
DataType_t data; //记录栈中存储数据
struct ChainStack *next; //记录当前节点直接后继节点的地址
}ChaStack_t;
-
创建一个空的链式栈，并为记录顺序栈信息的结构体申请堆内存，并进行初始化即可！
/******************************************************************** * * name : ChainStack_Create * function : 创建一个链式栈，栈顶应该连接有一个头结点，对该头结点进行初始化 * argument : * none * * retval : 调用成功返回已经完成初始化栈顶的头结点,否则退出程序 * author : [email protected] * date : 2024/04/25 * note : none * * *****************************************************************/ ChaStack_t *ChainStack_Create(void) { // 1.创建一个头结点并对头结点申请内存 ChaStack_t *Head = (ChaStack_t *)calloc(1, sizeof(ChaStack_t)); if (Head == NULL) { perror("Calloc memory for Head is Failed"); exit(-1); } // 2.对头结点进行初始化，头结点是不存储数据域，指针域指向NULL Head->next = NULL; // 3.把头结点的地址返回即可 return Head; } -
根据栈的特性，把新元素从栈顶入栈，也就是从链表的首部进行元素插入，操作如下：
/********************************************************************
*
* name : ChainStack_NewNode
* function : 创建新的结点，并对新结点进行初始化（数据域 + 指针域）
* argument :
* @data 新节点需要存储的数据
*
* retval : 调用成功返回已经完成初始化的链式栈的新节点,否则返回NULL
* author : [email protected]
* date : 2024/04/25
* note : none
*
* *****************************************************************/
ChaStack_t *ChainStack_NewNode(DataType_t data)
{
// 1.创建一个新结点并对新结点申请内存
ChaStack_t *New = (ChaStack_t *)calloc(1, sizeof(ChaStack_t));
if (NULL == New)
{
perror("Calloc memory for NewNode is Failed");
return NULL;
}
// 2.对新结点的数据域和指针域进行初始化
New->data = data;
New->next = NULL;
return New;
}
/********************************************************************
*
* name : ChainStack_Push
* function : 入栈，将要存储的数据，从栈顶入栈，即对链表进行头插操作
* argument :
* @Head 栈顶连接头结点
* @data 新节点的数据域需要存储的数据
*
* retval : 调用成功输出"插入成功"，否则输出"插入失败"
* author : [email protected]
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void ChainStack_Push(ChaStack_t *Head, DataType_t data)
{
// 定义一个循环指针变量Phead
ChaStack_t *Phead = Head->next;
// 调用函数创立一个新节点,并完成对应的错误处理
ChaStack_t *New = ChainStack_NewNode(data);
if (New == NULL)
{
printf("Push of %d is fail!\n", New->data);
return;
}
// 进行判断，排除空链表的情况
if (Head->next == NULL)
{
Head->next = New;
printf("Push of %d is success!\n", New->data);
return;
}
//1. 将新节点的next连接至首节点
New->next = Phead;
//2. 将头结点的next连接至新节点
Head->next = New;
printf("Push of %d is success!\n", New->data);
return;
}
-
根据栈的特性，把元素从栈顶出栈，也就是把元素从链表的首部将元素删除，操作如下：
/******************************************************************** * * name : CircLList_HeadDel * function : 出栈，将链式栈的栈顶元素删除，即链表的头删 * argument : * @Head 栈顶连接的头结点 * * retval : 调用成功后让栈顶的元素出栈 * author : [email protected] * date : 2024/04/25 * note : none * * *****************************************************************/ void ChainStack_Pop(ChaStack_t *Head) { // 对单向循环链表的头结点的地址进行备份 ChaStack_t *Phead = Head->next; // 判断当前链表是否为空，为空则直接退出 if (Head->next == NULL) { printf("current linkeflist is empty!\n"); return; } //1. 将头结点的next连接至首节点的直接后继 Head->next = Phead->next; //2. 将首节点的next指向NULL Phead->next = NULL; //3. 删除掉首节点 free(Phead); printf("Pop is success!\n"); return; } -
对链式栈中的元素进行遍历，只需要从链式栈的栈顶开始向栈底进行遍历，操作如下：
/********************************************************************
*
* name : ChainStack_Printf
* function : 遍历输出栈中已经存储的数据
* argument :
* @Head 栈顶连接的头结点
*
* retval : 调用成功输出链表中所有节点的数据域的值
* author : [email protected]
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void ChainStack_Printf(ChaStack_t *Head)
{
// 对单向循环链表的头结点的地址进行备份
ChaStack_t *Phead = Head;
// 判断当前链表是否为空，为空则直接退出
if (Head->next == NULL)
{
printf("current linkeflist is empty!\n");
return;
}
printf("Stack Top->");
// 从首结点开始遍历
while (Phead->next)
{
// 把头结点的直接后继作为新的头结点
Phead = Phead->next;
// 输出头结点的直接后继的数据域
printf("%d->", Phead->data);
// 判断是否到达尾结点，尾结点的next指针是指向首结点的地址
if (Phead->next == Head->next)
{
break;
}
}
printf("Stack Bottom\n");
return;
}
代码整体展示：
/*******************************************************************
*
* file name: ChainStack.c
* author : [email protected]
* date : 2024/04/25
* function : 该案例是掌握链式栈的创建原理与功能实现
* note : None
*
* CopyRight (c) 2023-2024 [email protected] All Right Reseverd
*
* *****************************************************************/
#include <stdio.h>
#include <stdlib.h>
//指的是链式栈中的元素的数据类型，用户可以根据需要进行修改
typedef int DataType_t;
//构造记录链式栈各项参数(栈中存储数据 + 栈顶元素的地址)的结构体
typedef struct ChainStack
{
DataType_t data; //记录栈中存储数据
struct ChainStack *next; //记录当前节点直接后继节点的地址
}ChaStack_t;
/********************************************************************
*
* name : ChainStack_Create
* function : 创建一个链式栈，栈顶应该连接有一个头结点，对该头结点进行初始化
* argument :
* none
*
* retval : 调用成功返回已经完成初始化栈顶的头结点,否则退出程序
* author : [email protected]
* date : 2024/04/25
* note : none
*
* *****************************************************************/
ChaStack_t *ChainStack_Create(void)
{
// 1.创建一个头结点并对头结点申请内存
ChaStack_t *Head = (ChaStack_t *)calloc(1, sizeof(ChaStack_t));
if (Head == NULL)
{
perror("Calloc memory for Head is Failed");
exit(-1);
}
// 2.对头结点进行初始化，头结点是不存储数据域，指针域指向NULL
Head->next = NULL;
// 3.把头结点的地址返回即可
return Head;
}
/********************************************************************
*
* name : ChainStack_NewNode
* function : 创建新的结点，并对新结点进行初始化（数据域 + 指针域）
* argument :
* @data 新节点需要存储的数据
*
* retval : 调用成功返回已经完成初始化的链式栈的新节点,否则返回NULL
* author : [email protected]
* date : 2024/04/25
* note : none
*
* *****************************************************************/
ChaStack_t *ChainStack_NewNode(DataType_t data)
{
// 1.创建一个新结点并对新结点申请内存
ChaStack_t *New = (ChaStack_t *)calloc(1, sizeof(ChaStack_t));
if (NULL == New)
{
perror("Calloc memory for NewNode is Failed");
return NULL;
}
// 2.对新结点的数据域和指针域进行初始化
New->data = data;
New->next = NULL;
return New;
}
/********************************************************************
*
* name : ChainStack_Push
* function : 入栈，将要存储的数据，从栈顶入栈，即对链表进行头插操作
* argument :
* @Head 栈顶连接头结点
* @data 新节点的数据域需要存储的数据
*
* retval : 调用成功输出"插入成功"，否则输出"插入失败"
* author : [email protected]
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void ChainStack_Push(ChaStack_t *Head, DataType_t data)
{
// 定义一个循环指针变量Phead
ChaStack_t *Phead = Head->next;
// 调用函数创立一个新节点,并完成对应的错误处理
ChaStack_t *New = ChainStack_NewNode(data);
if (New == NULL)
{
printf("Push of %d is fail!\n", New->data);
return;
}
// 进行判断，排除空链表的情况
if (Head->next == NULL)
{
Head->next = New;
printf("Push of %d is success!\n", New->data);
return;
}
//1. 将新节点的next连接至首节点
New->next = Phead;
//2. 将头结点的next连接至新节点
Head->next = New;
printf("Push of %d is success!\n", New->data);
return;
}
/********************************************************************
*
* name : CircLList_HeadDel
* function : 出栈，将链式栈的栈顶元素删除，即链表的头删
* argument :
* @Head 栈顶连接的头结点
*
* retval : 调用成功后让栈顶的元素出栈
* author : [email protected]
* date : 2024/04/25
* note : none
*
* *****************************************************************/
void ChainStack_Pop(ChaStack_t *Head)
{
// 对单向循环链表的头结点的地址进行备份
ChaStack_t *Phead = Head->next;
// 判断当前链表是否为空，为空则直接退出
if (Head->next == NULL)
{
printf("current linkeflist is empty!\n");
return;
}
//1. 将头结点的next连接至首节点的直接后继
Head->next = Phead->next;
//2. 将首节点的next指向NULL
Phead->next = NULL;
//3. 删除掉首节点
free(Phead);
printf("Pop is success!\n");
return;
}
/********************************************************************
*
* name : ChainStack_Printf
* function : 遍历输出栈中已经存储的数据
* argument :
* @Head 栈顶连接的头结点
*
* retval : 调用成功输出链表中所有节点的数据域的值
* author : [email protected]
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void ChainStack_Printf(ChaStack_t *Head)
{
// 对单向循环链表的头结点的地址进行备份
ChaStack_t *Phead = Head;
// 判断当前链表是否为空，为空则直接退出
if (Head->next == NULL)
{
printf("current linkeflist is empty!\n");
return;
}
printf("Stack Top->");
// 从首结点开始遍历
while (Phead->next)
{
// 把头结点的直接后继作为新的头结点
Phead = Phead->next;
// 输出头结点的直接后继的数据域
printf("%d->", Phead->data);
// 判断是否到达尾结点，尾结点的next指针是指向首结点的地址
if (Phead->next == Head->next)
{
break;
}
}
printf("Stack Bottom\n");
return;
}
int main()
{
//创立栈顶连接的头结点
ChaStack_t *Head = ChainStack_Create();
//入栈
ChainStack_Push(Head, 10);
ChainStack_Push(Head, 20);
ChainStack_Push(Head, 30);
printf("\n");
//遍历
ChainStack_Printf(Head);
//出栈
ChainStack_Pop(Head);
ChainStack_Pop(Head);
printf("\n");
//遍历
ChainStack_Printf(Head);
ChainStack_Pop(Head);
ChainStack_Pop(Head);
return 0;
}
结果验证：
热门相关：一级BOSS：你结婚，我劫婚 我写的书实在太毒了 纣临 弃妇种田忙 惊悚乐园