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

数据结构(链式栈)

news 来源：原创 2025/7/16 19:43:32

链式栈

链式栈（Linked Stack）是一种基于链表的数据结构，用于实现栈（后进先出，LIFO）的特性。与基于数组的栈不同，链式栈通过动态分配内存来存储数据，这使得它更加灵活，能够在运行时根据需要动态调整栈的大小。

以下是链式栈的基本结构和操作：

节点结构
链式栈的每个节点通常包含两个部分：数据域和指针域。数据域用于存储数据，指针域用于指向下一个节点。

typedef struct StackNode {int data;           // 数据域struct StackNode* next; // 指针域，指向下一个节点
} StackNode;

栈结构
栈结构通常包含一个指向栈顶节点的指针（即头指针）。

	typedef struct {StackNode* top;     // 指向栈顶节点的指针
} Stack;

初始化栈
初始化栈时，通常将栈顶指针设置为NULL，表示栈为空。

int LStack_init(LinkStack *st, int num){st -> pHead = NULL;st -> size  = num;st -> num   = 0;return 0 ;}

入栈操作（Push）
入栈操作是在栈顶添加一个新的节点。

int LStack_push(LinkStack *st,DATA data){if(LStack_isfull(st))return -1;NODE* p = (NODE*)malloc(sizeof(NODE));if(!p)return -1;p -> data   = data;p -> next   = st -> pHead;st -> pHead = p;(st -> num)++;return 0;}

出栈操作（Pop）
出栈操作是移除栈顶的节点，并返回其数据。

int LStack_pop(LinkStack *st,DATA *data){if(LStack_isempty(st))return -1;NODE* p = st -> pHead;if(!p)return -1;*data = p -> data;st -> pHead = p -> next;free(p);(st -> num)--;return 0;}

linkstack.h

 #ifndef __LINKSTACK_H#define __LINKSTACK_H// 数据类型
typedef   int   DATA;
// 链式栈节点
typedef    struct  _node{DATA       data; // 数据
struct _node *next; // 指向下一个栈的节点
}NODE;// 链式栈管理结构体
typedef  struct{NODE     *pHead;// 链式栈栈顶指针
int  size; // 链式栈当前元素个数
int  num;     
}LinkStack;// 初始化链式栈
int LStack_init(LinkStack *s, int num);// 判断栈是否已满
int LStack_isfull(LinkStack *st);// 判断栈是否为空
int LStack_isempty(LinkStack *st);// 压栈/入栈
int LStack_push(LinkStack *st,DATA data);// 弹栈/出栈
int LStack_pop(LinkStack *st,DATA *data);// 回收栈
int LStack_free(LinkStack *st);#endif

linkstack.c

 #include "linkstack.h"#include <stdio.h>#include <stdlib.h>// 初始化栈
int LStack_init(LinkStack *st, int num){st -> pHead = NULL;st -> size  = num;st -> num   = 0;return 0 ;}// 判断栈是否已满
int LStack_isfull(LinkStack *st){return st -> num == st -> size;}// 判断栈是否为空
int LStack_isempty(LinkStack *st){return st -> num == 0;}// 入栈
int LStack_push(LinkStack *st,DATA data){if(LStack_isfull(st))return -1;NODE* p = (NODE*)malloc(sizeof(NODE));if(!p)return -1;p -> data   = data;p -> next   = st -> pHead;st -> pHead = p;(st -> num)++;return 0;}// 出栈
int LStack_pop(LinkStack *st,DATA *data){if(LStack_isempty(st))return -1;NODE* p = st -> pHead;if(!p)return -1;*data = p -> data;st -> pHead = p -> next;free(p);(st -> num)--;return 0;}// 回收栈
int LStack_free(LinkStack *st){NODE* p = st -> pHead, *q = NULL;while(p){q  = p;p  = p -> next;free(q);       }st -> pHead = NULL;st -> num   = 0;return 0;}

LStack_init: 初始化栈，将栈的头指针指向空，设置栈的最大容量和当前元素个数为0。

LStack_isfull: 判断栈是否已满，即判断当前元素个数是否等于最大容量。

LStack_isempty: 判断栈是否为空，即判断当前元素个数是否为0。

LStack_push: 入栈操作，首先判断栈是否已满，如果已满则返回-1表示入栈失败。否则，创建一个新的节点，将数据放入节点的data字段，将节点的next指针指向原来的栈顶节点，并更新栈顶指针为新节点，同时将当前元素个数加1。

LStack_pop: 出栈操作，首先判断栈是否为空，如果为空则返回-1表示出栈失败。否则，将栈顶节点的数据存入指定的data变量中，更新栈顶指针为原栈顶的下一个节点，并释放原栈顶节点的内存，同时将当前元素个数减1。

LStack_free: 回收栈，释放栈中所有节点的内存，将栈的头指针指向空，将当前元素个数设置为0。

linkstack_main.c

 #include "linkstack.h"#include <stdio.h>int main(void){LinkStack  st;LStack_init(&st,10);register int i = 1;for(; i <= 10; i++)LStack_push(&st,i);if(-1 == LStack_push(&st,1024))fprintf(stderr,"满栈,插入失败\n");while(!LStack_isempty(&st)){DATA   data = 0;LStack_pop(&st,&data);printf("%4d",data);         }printf("\n");LStack_free(&st);return 0;  
}

练习 2 」

使用链式栈，实现十进制转八进制：键盘输入一个十进制数，经过链式栈的相关算法，输出八进制数。

在这里插入图片描述

解析：首先需要构建一个链式栈，链式栈实际上就是一条链表，只不过只能对栈顶操作。然后再将与栈相关的数据封装在一个统一的结构体中，方便管理，比如可以这样设计链栈的节点和链栈的管理结构体:

 #include <stdio.h>#include <stdlib.h>#include <stdbool.h>// 链栈的节点（实际上就是单链表节点）
struct node{int data;struct node *next;};// 链栈管理结构体
typedef struct{struct node *top;int size;}linkstack;// 初始化空栈
linkstack *init_stack(void){linkstack *s = malloc(sizeof(linkstack));if(s != NULL){s->top = NULL;s->size = 0;}return s;}}// 入栈
void push(int data, linkstack *s){struct node *new = malloc(sizeof(struct node));if(new != NULL){new->data = data;}new->next = s->top;s->top = new;s->size++;// 判断栈是否为空
bool is_empty(linkstack *s){return s->size == 0;}// 出栈
bool pop(linkstack *s, int *pm){if(is_empty(s))return false;*pm = s->top->data;struct node *tmp = s->top;s->top = s->top->next;free(tmp);s->size--;return true;}int main(int argc, char const *argv[]){linkstack *s = init_stack();int n;scanf("%d", &n);while(n > 0){push(n%8, s);n /= 8;}int m;printf("0");while(1){if(is_empty(s))break;pop(s, &m);printf("%d", m);}printf("\n");return 0;}

首先定义了一个链栈的节点结构体，包含数据和指向下一个节点的指针。

然后定义了链栈管理结构体，包含了栈顶指针和栈的大小。

接着实现了初始化空栈的方法，通过动态分配内存来创建一个链栈管理结构体，并初始化栈顶指针为空，栈的大小为0。

然后实现了入栈的方法，首先动态分配内存来创建一个新的节点，然后将数据赋值给节点的data成员，将当前栈顶指针赋值给节点的next成员，最后将新节点设置为栈顶指针，并将栈的大小加1。

接着实现了判断栈是否为空的方法，通过判断栈的大小是否为0来确定栈是否为空。

然后实现了出栈的方法，首先判断栈是否为空，如果为空则返回false，否则将栈顶节点的数据赋值给传入的指针变量pm，并将栈顶指针指向下一个节点，释放原来的栈顶节点的内存，最后将栈的大小减1，返回true表示出栈成功。

最后在main函数中，首先调用init_stack方法初始化一个空栈，然后读取输入的十进制数n，将n转换为八进制数并依次入栈，最后循环出栈并打印栈中的数据，直到栈为空。

链式栈

练习 2 」

相关文章：