数据结构之栈和队列（一）

本文主要介绍2种操作受限的线性表结构：栈（Stack）和队列（Queue），包括它们的概念和存储结构。 除此之外，还会简单介绍一下特殊矩阵的压缩存储。

栈（Stack）

栈是只允许在一端进行插入或删除操作的线性表。它满足后进先出（LIFO）。

栈的基本操作：

1. InitStack(&S)：初始化
2. StackEmpty(S)：判断栈是否为空
3. Push(&S,x)：进栈，若栈S未满，将x加入使之成为新的栈顶
4. Pop(&S,x)：出栈，若栈S非空，弹出栈顶元素，并用x返回
5. GetTop(S,&x)：读栈顶元素，若栈S非空，用x返回栈顶元素
6. ClearStack(&S)：销毁栈，释放S存储空间

栈的顺序存储

栈的顺序存储也称顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时设有一个**指针（top）**指示当前栈顶的位置。

栈的顺序存储类型描述如下：

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];
    int top;
}SqStack;

栈顶指针（top）初始值不同，进栈出栈操作也有所不同，栈顶指针初始值一般取-1或0，对应操作如下：

初始化栈

void InitStack(&S){
    s.top==-1;           //初始化栈顶指针
}

判栈空

bool StackEmpty(S){
    if(s.top==-1)
        return true;      //栈空
    else
        return false;
}

进栈

bool Push(SqStack &S,ElemType x){
    if(s.top==MaxSize-1)    //栈满报错
        return false;
    S.data[++S.top]=x;     //指针先加1，再进栈
    return true;
}

出栈

bool Pop(SqStack &S,ElemType x){
    if(s.top==-1)           //栈空报错
        return false;
    x=S.data[S.top--];     //先出栈，指针再减1
    return true;
}

读取栈顶元素

bool GetTop(SqStack &S,ElemType &x){
    if(S.top==-1)            //栈空报错
        return false;
    x=S.data[S.top];        //x记录栈顶元素
    return true;
}

栈的链式存储

链式存储的栈又称链栈，优点是便于多个栈共享存储空间，提高效率，并且不存在栈满上溢情况。

1. 常采用单链表实现，规定操作都是在单链表的表头进行
2. 一般规定链栈没有头结点，Lhead指向栈顶元素

栈的链式存储类型描述如下：

typedef struct Linknode{
    ElemType data;            //数据域
    struct Linknode *next;   //指针域
}*LiStack;

共享栈

共享栈是为了高效的利用存储空间。利用栈底的位置相对不变这一特性，我们可以让2个顺序栈共享一个一维数据空间。这2个栈的栈底分别设在共享空间的两端，两个栈顶向共享空间延伸。

2个栈的进出栈操作如下图所示：