数据结构——链式栈c代码实现

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

• 前言
• • 1.头文件
  • 2.源文件
  • 3.注意

链栈：

链式栈是一种数据存储结构，可以通过单链表的方式来实现，使用链式栈的优点在于它能够克服用数组实现的顺序栈空间利用率不高的特点，但是需要为每个栈元素分配额外的指针空间用来存放指针域。

#include
#include
#include

//栈(链栈)
//实现了简单的链栈操作，包括初始化，压栈，弹栈，获取栈顶元素，打印，清空



typedef struct Node{
    int data;
    struct Node *next;
} node;


typedef struct LinkStack{
    node *head;  //虚拟头结点
    node *top;   //栈顶节点
    int size;
} link_stack;



//创建node
node *GetNewNode(int val);

// 初始化一个空的栈
link_stack *InitLinkStack();

//压栈
int LinkStackPush(link_stack *stack, int x);

//弹栈
int LinkStackPop(link_stack *stack);

//获取栈顶元素
int GetLinkStackTop(link_stack *stack);

//打印
void PrintLinkStack(link_stack *stack);

//删除栈
void DeleteLinkStack(link_stack *stack);

代码如下（示例）：

#include "link_stack.h"

//创建node
node *GetNewNode(int val)
{
    node *p = (node *)malloc(sizeof(node));
    p->data = val;
    p->next = NULL;
    return p;
}

// 初始化一个空的栈
link_stack *InitLinkStack()
{
    link_stack *stack = (link_stack *)malloc(sizeof(link_stack));
    stack->head = GetNewNode(0);
    stack->top = stack->head;
    stack->size = 0;
    return stack;
}

//压栈
int LinkStackPush(link_stack *stack, int x)
{
    assert(stack != NULL);
    node *newNode = GetNewNode(x);
    stack->top->next = newNode;
    stack->top = newNode;
    stack->size++;
    return 0;
}

//弹栈
int LinkStackPop(link_stack *stack)
{
    assert(stack != NULL);
    if (stack->size == 0)
    {
        printf("栈空了，无法弹栈n");
        return -1;
    }
    node *p = stack->head;
    while (p->next != stack->top)
    {
        p = p->next;
    }
    free(stack->top);
    stack->top = p;
    stack->top->next = NULL;
    stack->size--;
    return 0;
}

//获取栈顶元素
int GetLinkStackTop(link_stack *stack)
{
    assert(stack != NULL);
    if (stack->size == 0)
    {
        printf("栈为空，没有元素可获取n");
        return -1;
    }
    return stack->top->data;
}

//打印
void PrintLinkStack(link_stack *stack)
{
    printf("------------size = %d--------------------n", stack->size);
    node *p = stack->head->next;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("n-----------------------------------------n");
}

//删除栈
void DeleteLinkStack(link_stack *stack)
{
    assert(stack != NULL);
    node *p = stack->head;
    node *q = p->next;
    while (q != NULL)
    {
        free(p);
        p = q;
        q = p->next;
    }
    free(p);
    free(stack);
    stack->head = NULL;
    stack->top = NULL;
    stack->size = 0;
}

int main()
{
    link_stack *stack = InitLinkStack();
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int x;
        scanf("%d", &x);
        if (x == 0)
        { //压栈
            scanf("%d", &x);
            LinkStackPush(stack, x);
        }
        else if (x == 1)
        { //弹栈
            LinkStackPop(stack);
        }
        else if (x == 2)
        { //获取栈顶元素
            printf("%dn", GetLinkStackTop(stack));
        }
        PrintLinkStack(stack);
    }
    DeleteLinkStack(stack);
    return 0;
}

1.博客中标注原创的文章，版权归作者所有；
2.未经作者允许不得转载本文内容，否则将视为侵权；
3.转载或者引用本文内容请注明来源及原作者；
4.对于不遵守此声明或者其他违法使用本文内容者，本人依法保留追究权等。