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

朴灿烈づ我的快乐病毒、 2022-02-25 02:16 288阅读 0赞

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

![1.png][]

### 栈（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**，对应操作如下：

![2.png][]

**初始化栈**

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指向栈顶元素

![3.png][]

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

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

### 共享栈 ###

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

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

![4.png][]

[1.png]: /images/20220225/d990f06900114dc7a002330872bf6427.png
[2.png]: /images/20220225/5a92ac315b714eac9602a524d7d471e7.png
[3.png]: /images/20220225/737c8b932a58499a88f5775fa1b9447f.png
[4.png]: /images/20220225/e8f5c8bd8bf94d7b8e6ea96dea5d805f.png