3. 栈、队列和数组

3.1 栈和队列的基本概念

3.2 栈和队列的顺序存储结构

3.3 栈和队列的链式存储结构

3.4 多维数组的存储

3.5 特殊矩阵的压缩存储

3.6 栈、队列和数组的应用

顺序存储实现栈

#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <iostream>

#define MaxSize 50
typedef int ElementType;

typedef struct{
    ElementType data[MaxSize];
    int top; // 栈顶 （表示最后一个元素的索引值）
}SqStack;

// 初始化栈
void InitStack(SqStack &S){
    S.top = -1; // 当 栈顶元素为 -1 时，表示栈为空
}

// 判断栈是否为空
bool StackEmpty(SqStack S) {
    if(S.top == -1) return true;
    return false;
}

// 入栈
bool Push(SqStack &S, ElementType e){
    if(S.top >= MaxSize-1) {
        return false; // 栈满了
    }
    S.data[++S.top] = e;
    return true;
}

// 出栈
bool Pop(SqStack &S, ElementType &e){
    if(StackEmpty(S)){
        return false;
    }
    e = S.data[S.top--];
    return true;
}


// 获取栈顶元素
bool GetTop(SqStack S, ElementType &e){
    if(StackEmpty(S)) return false;
    e = S.data[S.top];
    return true;
}



int main() {
    SqStack S;
    bool flag;
    InitStack(S);
    flag = StackEmpty(S);
    if(flag) {
        puts("栈为空");
    }


    Push(S, 3);
    Push(S, 4);
    Push(S, 5);
    ElementType m;
    flag = GetTop(S, m); // 获取栈顶元素

    if(flag) {
        printf("栈顶元素为：%d\n", m);
    }
    else {
        printf("栈顶元素为空");
    }

    flag = Pop(S, m);
    if(flag) {
        printf("弹出的栈元素为%d\n", m);
    }
  
}

使用链表实现栈

链表实现栈的思路：用头部插入法和头部删除法。