数据结构中有一种结构称为栈，而linux内存中的栈空间就是基于此设计的，栈内存自顶向下递增，其实栈和顺序表和链式表都一样，都属于线性结构，存储的数据的逻辑关系也是一对一的。
只不过栈是一种特殊的线性表，特殊在栈的一端是封闭的，数据的插入和删除只能在栈的另一端进行，也就是栈遵循”后进先出“的原则。也被称为”LIFO“结构，意思是”lase input first output“。出栈（POP）,入栈为（PUSH）
栈就像摞起来的盘子，我们都是从最上面开始拿取
闭合的一端被称为栈底（stack bottom）,允许数据的插入与删除的一段被称为栈顶（stack top）,不包含任何元素的栈被称为空栈
把数据插入到栈空间的动作被称为入栈或者压栈
从栈空间中删除数据的动作被称为出栈或者弹栈
由于栈也是一种线性结构，所以可以以数组或者链表作为基础，在此基础上实现栈的操作。
1.以数组作为基础实现栈空间（顺序栈）
数组在内存中占用一块连续的空间，也就是数组元素的内存地址是连续的。为了实现栈，一般是把数组头作为栈底，数组头部到数组尾部作为栈的增长方向，也就是用户只在数组尾部对数据进行插入和删除。
栈实现
sequentialstack.h
/**
*@file : sequentialstack
*@brief : 创建顺序栈，并实现栈的压栈和出栈并实现栈数据的遍历
*@author : TingFengLuo@126.com
*@date : 2025-12-28
*@version : V1.0
*@note : NULL
* */
#ifndef __SEQUENTIALSTACK_H_
#define __SEQUENTIALSTACK_H_
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
//将数据类型定义别名尾DataType_t，便于用户后续方便修改
typedef int DataType_t;
//将之后元素下标类型定义别名为SEQ_STACKCAPACITY_t,
typedef unsigned int SEQ_STACKCAPALAST_t;
//构造顺序栈类型
typedef struct Sequential_Stack{
//构造顺序栈中需要元素的个数
DataType_t capacity;
//构造顺序栈中最后元素的下标
SEQ_STACKCAPALAST_t top;
//构造顺序栈中的栈底地址
DataType_t *bottom;
}SeqStack_t;
//创建栈并初始化栈
SeqStack_t * Sqestack_create(unsigned int capacity);
//压栈
bool SeqStack_Push(SeqStack_t *stack,DataType_t data);
//判断栈是否为空
bool SeqStack_IsEmpty(SeqStack_t *stack);
//出栈
DataType_t SeqStack_Pop(SeqStack_t *stack);
//遍历栈
void SeqStack_show(SeqStack_t *stack);
#endif
sequentialstack.c
#include "sequentialstack.h"
/**
* @name : Sqestack_create
* @brief : 创建一个指定容量的空顺序栈
* @param
@capacity : 栈的最大容量
* @retval : 创建成功返回循环单链表类型的头节点地址，否则返回NULL
* @date : 2025-12-28
* @version 1.0 : V1.0
* @note : 栈中有元素个数，元素容量，栈首地址
*/
SeqStack_t * Sqestack_create(unsigned int capacity)
{
//分配栈结构本身内存
SeqStack_t *stack = calloc(1,sizeof(SeqStack_t));
if(NULL == stack){
perror("Sequential stack create memory failed for stack");
return NULL;
}
//分配栈的底层数据存储空间
stack->bottom = (DataType_t *)calloc(capacity,sizeof(DataType_t));
//判断底层数据是否被创建成功，如果失败释放stack内存，并退出程序
if(NULL == stack->bottom){
perror("Sequential stack create memory failed for bottom in stack");
free(stack);
return NULL;
}
//初始化栈元素的值；创建栈为空，所以栈最后元素的下标的-1
stack->capacity = capacity;
stack->top = -1;
//创建成功，返回栈地址
return stack;
}
/**
* @name : SeqStack_IsEmpty
* @brief : 判断栈是否为空返回true，否则返回false
* @param
@stack : 表示要操作的栈
* @retval : 如果为空
* @date : 2025-12-28
* @version 1.0 : V1.0
* @note : 单链表创建中头节点中是没有数据域的，所以数据域没有初始化
*/
bool SeqStack_IsEmpty(SeqStack_t *stack)
{
return stack->top == -1 ? true : false;
}
/**
* @name : SeqStack_Push
* @brief : 将数据压入栈中
* @param
@stack : 要操作的栈
@data : 要压入栈中的数据
* @retval : 压入成功返回true,否则返回false
* @date : 2025-12-10
* @version 1.0 : V1.0
* @note : 判断栈中是否满，如果栈满了直接返回false，否则进行压栈操作
*/
bool SeqStack_Push(SeqStack_t *stack,DataType_t data)
{
//判断栈是否存在
if(NULL == stack){
printf("Sequential stack create memory failed for stack\n");
return false;
}
//判断栈是否满
if(stack->capacity == stack->top+1){
printf("Sequential stack is full!!\n");
return false;
}
//将数据压入到栈中
stack->bottom[++stack->top] = data;
return true;
}
/**
* @name : SeqStack_Pop
* @brief : 出栈
* @param
@stack : 要操作的栈
* @retval : 返回出栈的数据
* @date : 2025-12-10
* @version 1.0 : V1.0
* @note : 判断栈是否为空，如果为空，直接返回false,否则栈顶元素-1
*/
DataType_t SeqStack_Pop(SeqStack_t *stack)
{
//创建变量用于存储出栈的值
DataType_t temp =0;
//判断顺序栈是否存在
if(NULL == stack){
printf("Sequentical stack create stack failed\n");
return false;
}
//判断栈是否为空
if(SeqStack_IsEmpty(stack)){
printf("Sequential stack is Empty!!\n");
return false;
}
//出栈
temp = stack->bottom[stack->top--];
return temp;
}
/**
* @name : SeqStack_show
* @brief : 遍历栈
* @param
@stack : 要操作的栈
* @retval : NULL
* @date : 2025-12-10
* @version 1.0 : V1.0
* @note : 判断栈是否存在，如果存在，直接遍历
*/
void SeqStack_show(SeqStack_t *stack)
{
if(NULL == stack){
printf("Sequential stack create stack failed\n");
return;
}
//遍历栈
for(int i = 0;i <= stack->top; i++){
printf("%d ",stack->bottom[i]);
}
printf("\n");
}
main.c
#include "sequentialstack.h"
int main(int argc,char * const argv[]){
//创建变量用于存储顺序栈的地址
SeqStack_t * stack = Sqestack_create(20);
if(stack == NULL ){
printf("create stack failed\n");
return -1;
}
printf("入栈数据：");
SeqStack_Push(stack,10);
SeqStack_Push(stack,20);
SeqStack_Push(stack,30);
SeqStack_Push(stack,40);
SeqStack_Push(stack,50);
SeqStack_show(stack);
printf("---------------------------------\n");
printf("出栈数据：");
//创建变量用于出栈的数据
DataType_t temp=0;
for(int i=0;i<5;i++){
temp = SeqStack_Pop(stack);
printf("%d " ,temp);
}
printf("\n");
printf("---------------------------------\n");
SeqStack_Push(stack,11);
temp = SeqStack_Pop(stack);
printf("%d ",temp);
SeqStack_Push(stack,12);
SeqStack_Push(stack,13);
SeqStack_Push(stack,14);
SeqStack_Push(stack,15);
while(!SeqStack_IsEmpty(stack)){
temp = SeqStack_Pop(stack);
printf("%d ",temp);
}
printf("\n");
printf("---------------------------------\n");
return 0;
}
效果如下：
设计一个进制转换程序，使用顺序栈设计一个把十进制数转换为十六进制数的接口实现当通过键盘输入一个非负的十进制数，可以在终端输出对应的十六进制数
void SeqStack_Dec2Hex(SeqStack_t *stack,unsigned int num)
{
if(NULL == stack){
printf("Sequential stack create memory failed for stack\n");
return;
}
//定义一个变量存储余数
int remainder;
do{
remainder = num % 16;
if(remainder <= 9){
SeqStack_Push(stack,remainder+'0');
}else{
SeqStack_Push(stack,remainder+'A'-10);
}
}while(num /= 16);
printf("0x");
while(!SeqStack_IsEmpty(stack)){
printf("%c",SeqStack_Pop(stack));
}
printf("\n");
}
效果：
通过键盘输入一个包括'(‘和’)’的字符串string，判断字符串是否有效。
void SeqStack_Dec2Hex(SeqStack_t *stack,unsigned int num)
{
if(NULL == stack){
printf("Sequential stack create memory failed for stack\n");
return;
}
//定义一个变量存储余数
int remainder;
do{
remainder = num % 16;
if(remainder <= 9){
SeqStack_Push(stack,remainder+'0');
}else{
SeqStack_Push(stack,remainder+'A'-10);
}
}while(num /= 16);
printf("0x");
while(!SeqStack_IsEmpty(stack)){
printf("%c",SeqStack_Pop(stack));
}
printf("\n");
}
发表回复