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

数据结构（七）---链式栈

news 2025/4/28 11:22:20

#### 链式栈实现

##### linkstack.h

#ifndef _LINKSTACK_H
#define _LINKSTACK_H

// 引入相关的库文件
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定义元素类型的别名
typedef int DATA;

//定义链式栈节点
typedef struct node
{
DATA data;
struct node *next;
}NODE;

//定义链式栈结构体
typedef struct
{
   NODE *top; //栈顶指针，其实就是链表中的头节点
   int size; //当前元素数量
   int capacity; //栈容量
}LinkStack;

/**
* 初始化链式栈
* @param s 栈结构体指针（需由调用者提前分配内存）
* @param num 栈容量的大小
* @return 初始化成功返回0，否则返回-1
*/
extern int lstack_init(LinkStack *s, int num);

/**
* 判断栈是否已满
* @param s 栈结构体指针（需由调用者提前分配内存）
* @return 栈已满返回1
*/
extern int lstack_isfull(LinkStack *s);

/**
* 入栈
* @param s 栈结构体指针（需由调用者提前分配内存）
* @param data 待入栈的数据
* @return 成功返回0，否则返回-1
*/
extern int lstack_push(LinkStack *s, DATA data);

/**
* 判断栈是否为空
* @param s 栈结构体指针（需由调用者提前分配内存）
* @return 栈为空返回1
*/
extern int lstack_isempty(LinkStack *s);

/**
* 出栈
* @param s 栈结构体指针（需由调用者提前分配内存）
* @param data 接收出栈的数据指针
* @return 成功返回0，否则返回-1
*/
extern int lstack_pop(LinkStack *s, DATA *data);

/**
* 销毁栈
*/
extern void lstack_destroy(LinkStack *s);

#endif //_LINKSTACK_H
```

##### linkstack.c

#include "linkstack.h"

/**
* 初始化链式栈
* @param s 栈结构体指针（需由调用者提前分配内存）
* @param num 栈容量的大小
* @return 初始化成功返回0，否则返回-1
*/
int lstack_init(LinkStack *s, int num)
{
   //空指针检查
   if(!s)
   {
       perror("创建失败！");
       return -1;
   }

   //num的检查
   if(num <= 0)
   {
       perror("容量有误，创建失败！");
       return -1;
   }

   //初始化栈属性
   s->top = NULL; //栈顶指针置空，表示空栈
   s->size = 0; //当前元素数量为0
   s->capacity = num; //设置容量限制（需后续操作中校验）

   return 0;
}

/**
* 判断栈是否已满
* @param s 栈结构体指针（需由调用者提前分配内存）
* @return 栈已满返回1
*/
int lstack_isfull(LinkStack *s)
{
return s->size >= s->capacity;
}

/**
* 入栈
* @param s 栈结构体指针（需由调用者提前分配内存）
* @param data 待入栈的数据
* @return 成功返回0，否则返回-1
*/
int lstack_push(LinkStack *s, DATA data)
{
   //判断栈是否已满
   if(lstack_isfull(s))
   {
       perror("栈已满，数据无法入栈！");
       return -1;
   }

   //创建新节点
   NODE *p = (NODE*)malloc(sizeof(NODE));
   if(!p)
   {
       perror("Memory allocation failed!");
       return -1;
   }

   //初始化
   p->data = data; //存储数据
   p->next = s->top; //新节点指向原栈顶
   s->top = p; //更新栈顶指针为新节点
   s->size++; //元素计数增加

   return 0;
}

/**
* 判断栈是否为空
* @param s 栈结构体指针（需由调用者提前分配内存）
* @return 栈为空返回1
*/
int lstack_isempty(LinkStack *s)
{
   if(!s)
       return 1; //空指针视为空栈

   return s->size == 0;
   //return s->top = NULL;
}

/**
* 出栈
* @param s 栈结构体指针（需由调用者提前分配内存）
* @param data 接收出栈的数据指针
* @return 成功返回0，否则返回-1
*/
int lstack_pop(LinkStack *s, DATA *data)
{
   if(!s || !data)
   {
       perror("Stack is empty！");
       return -1;
   }

   //判断栈是否为空
   if(lstack_isempty(s))
   {
       perror("警告！试图从空栈弹出数据！");
       return -1;
   }

   NODE *p = s->top; //保存栈顶节点
   *data = p->data; //获取弹出栈的数据
   s->top = p->next; //更新栈顶指针
   free(p); //释放原栈顶节点
   s->size--;

   return 0;
}

/**
* 销毁栈
*/
void lstack_destroy(LinkStack *s)
{
   if(!s)
       return; //空指针保护

   DATA temp; //临时存储弹出数据

   //释放所有节点
   while(!lstack_isempty(s))
   {
       lstack_pop(s, &temp); //弹出数据存入temp
   }
   return;
}
```