数据结构-栈的灵活表示方式(栈顶指针和栈底指针)

分手后的思念是犯贱 2022-05-04 00:26 220阅读 0赞

在前面的文章中我们已经学习过基本栈的概念和操作，我们是通过“标准方式”数组的形式模拟了一个栈；本篇文章我将通过一种更灵活的方式定义栈以及实现栈的基本操作，废话不多说，直接上代码（注释都有说明哦）

//栈的灵活表示法，通过定义栈顶指针和栈底指针的方式
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #define ElementType int
    #define MaxSize 10
    
    //定义栈的结构体
    typedef struct {
        ElementType *top;//栈顶指针（这里定义为指向栈顶元素的下一个位置，即为空）
        ElementType *base;//栈底指针
        int stackSize;//栈的容量
    } Stack;
    
    /**
     *  初始化栈
     * @param s
     */
    void InitStack(Stack *s) {
        //初始化分配栈的总空间
        s->base = (ElementType *) malloc(MaxSize * sizeof(ElementType));
        if (!s->base) {
            exit(0);
        }
        s->top = s->base;
        s->stackSize = MaxSize;
    }
    
    /**
     * 入栈
     * @param s 栈
     * @param e 入栈元素
     */
    void Push(Stack *s, ElementType e) {
        //判断栈是否已满
        ElementType p = s->top - s->base;
        if (p >= MaxSize) {
            //栈已满
            //处理方式1.递增空间 2.退出
            exit(0);
        }
        *(s->top) = e;//赋值
        s->top++;//栈顶指针上移
    }
    
    /**
     * 出栈
     * @param s 栈
     * @return
     */
    ElementType Pop(Stack *s) {
        //判断栈是否为空
        if (s->top == s->base) {
            //栈为空
            printf("不好意思，栈目前为空~");
            exit(0);
        }
        s->top--;//栈顶指针下移
        ElementType e = *(s->top);//取值，并不是取地址
        return e;
    }
    
    /**
     * 栈大小
     * @param s 栈
     * @param len
     */
    ElementType GetLen(Stack s) {
        return (s.top - s.base);
    }
    
    /**
     * 清空栈
     * @param s
     */
    void ClearStack(Stack *s) {
        s->top = s->base;
    }
    
    /**
     * 销毁栈
     * @param s
     */
    void DestoryStack(Stack *s) {
        s->top = s->base;
        free(s->base);
        s->stackSize = 0;
    }
    
    int main() {
        printf("Hello, World!\n");
        Stack stack;
        int len;
        InitStack(&stack);
        len = GetLen(stack);
        printf("当前栈长度 len=%d\n", len);
        int temp = 10;
        int value;
        printf("入栈 value=%d\n", temp);
        Push(&stack, temp);
        len = GetLen(stack);
        printf("当前栈长度 len=%d\n", len);
        value = Pop(&stack);
        printf("出栈 value=%d\n", value);
        len = GetLen(stack);
        printf("出栈后栈长度 len=%d\n", len);
        return 0;
    }

![70][]

[70]: /images/20220504/f9afb0feb7d940e18f11471177844016.png