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

数据结构(链式栈)

article 2025/1/3 21:03:48

链式栈

链式栈（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;
 }