阅读:0       作者:解学武

栈的基本操作及C语言代码实现

由于本身是一种特殊的线性表(遵循“先入先出”原则),因此栈的实现由两种方式,顺序栈(通过数组实现)链栈(通过链表实现)

栈操作数据元素只有两种动作:
  1. 数据元素用栈的数据结构存储起来,称为“入栈”,也叫“压栈”
  2. 数据元素由于某种原因需要从栈结构中提取出来,称为“出栈”,也叫“弹栈”

顺序栈

顺序栈的实现采用的是数组。

在顺序栈中设定一个随时指向栈顶元素的变量(一般命名为 top ),当 top 的值为 -1 时,说明数组中没有数据,即栈中没有数据元素,为“空栈”;只要数据元素进栈,top 就加 1 ;数据元素出栈, top 就减 1 。

例如,使用顺序栈的存储结构将 ('a','b','c','d') 四个元素逐个压栈并输出栈顶元素。

实现代码:
#include <stdio.h>
//元素elem进栈
int push(char* a,int top,char elem){
    a[++top]=elem;
    return top;
}
//数据元素出栈
int pop(char * a,int top){
    if (top==-1) {
        printf("空栈");
        return -1;
    }
    printf("弹栈元素:%c\n",a[top]);
    top--;
    return top;
}
int main() {
    char a[100];
    int top=-1;
    top=push(a, top, 'a');
    top=push(a, top, 'b');
    top=push(a, top, 'c');
    top=push(a, top, 'd');
    top=pop(a, top);
    top=pop(a, top);
    top=pop(a, top);
    top=pop(a, top);
    top=pop(a, top);
    return 0;
}
输出结果:
弹栈元素:d
弹栈元素:c
弹栈元素:b
弹栈元素:a
空栈

链栈

链栈,用线性表的链式存储结构实现。

链栈一般不需要创建头结点,头结点会增加程序的复杂性,只需要创建一个头指针就可以了。

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

例如,用链栈实现将 ('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 栈已空
栈内没有元素