美文网首页
数据结构——栈

数据结构——栈

作者: 翼动晴空 | 来源:发表于2017-05-14 12:36 被阅读65次

    一、概念
    :栈是一个先进后出的线性表,它要求只在表尾进行删除和插入等操作。

    所以栈其实就是一个线性表,不过操作有特殊的要求和限制:

    1. 元素必须先进后出;
    2. 操作只能在线性表尾进行

    栈的基本操作只有2个

    • 入栈(Push)
    • 出栈(Pop)

    栈的结构示意图(网上找的)


    栈的结构示意图

    二、栈的实现

    下面介绍如何使用顺序表实现一个简单的栈

    (1)定义栈的结构

    typedef struct {
        DATA data[SIZE+1]; //栈的数据元素,SIZE表示栈大小,数据从下标1开始保存
        int top; //栈顶,top=0时表示栈为空
    }SeqStack;
    

    (2)初始化栈

    SeqStack *SeqStackinit()
    {
        SeqStack *p;
        if (p=(SeqStack *)malloc(sizeof(SeqStack))) {
            p->top = 0;
            return p;
        }
        return NULL;
    }
    
    

    (3)释放栈

    void SeqStackFree(SeqStack *s)
    {
        if (s)
            free(s);
    }
    
    

    (4)判断栈的状态

    int SeqStackIsEmpty(SeqStack *s)
    {
        return (s->top == 0);
    }
    
    void SeqStackClear(SeqStack *s)
    {
        s->top = 0;
    }
    
    int SeqStackIsFull(SeqStack *s)
    {
        return (s->top == SIZE);
    }
    

    (5)入栈

    int SeqStackPush(SeqStack *s, DATA data)
    {
        if ((s->top + 1) > SIZE) {
            printf("栈溢出\n");
            return 0;
        }
    
        s->data[++s->top] = data;
        return 1;
    }
    

    (6)出栈

    DATA SeqStackPop(SeqStack *s)
    {
        if (s->top == 0) {
            printf("栈为空\n");
            exit(0);
        }
    
        return (s->data[s->top--]);
    }
    

    (7)获取栈顶元素

    DATA SeqStackPeek(SeqStack *s)
    {
        if (s->top == 0) {
                printf("栈为空\n");
                exit(0);
        }
        return (s->data[s->top]);
    }
    

    打完手工,可能有不完善或者bug,只能等以后发现了再修改了

    相关文章

      网友评论

          本文标题:数据结构——栈

          本文链接:https://www.haomeiwen.com/subject/iwcqxxtx.html