阅读:0       作者:严长生

链栈的基本操作(入栈和出栈)及C语言实现完全攻略

链栈,即用线性表链表结构实现的功能。实现过程中,链栈不需要创建头结点,增加头结点反而会增加程序的复杂性,因此链表中只需要创建一个头指针就可以了。

链栈的实现思想是:用链表头结点的一端作为栈的栈顶端,这样做的好处是当数据元素压栈或者弹栈时,直接使用头指针就可以完成,不需要增设额外的指针。

例如,用链栈实现将(’a’,’b’,’c’,’d’)四个数据元素压栈,再依次弹栈:
#include <stdio.h>
#include <stdlib.h>
//链表结点的结构
typedef struct lineStack{
    char data;
    struct lineStack * next;
}lineStack;
//实现入栈操作,向链表的表头添加新增元素
lineStack* push(lineStack * stack,char a){
    lineStack * line=(lineStack*)malloc(sizeof(lineStack));
    line->data=a;
    line->next=stack;
    stack=line;
    return stack;
}
//实现出栈操作
lineStack * pop(lineStack * stack){
    if (stack) {
        lineStack * p=stack;
        stack=stack->next;
        printf("弹栈元素:%c ",p->data);
        if (stack) {
            printf("栈顶元素:%c\n",stack->data);
        }else{
            printf("栈已空\n");
        }
        free(p);
    }else{
        printf("栈内没有元素");
        return stack;
    }
    return stack;
}
int main() {
    lineStack * stack=NULL;
    stack=push(stack, 'a');
    stack=push(stack, 'b');
    stack=push(stack, 'c');
    stack=push(stack, 'd');
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    return 0;
}
输出结果:
弹栈元素:d 栈顶元素:c
弹栈元素:c 栈顶元素:b
弹栈元素:b 栈顶元素:a
弹栈元素:a 栈已空
栈内没有元素