数据结构第5讲顺序栈

叁歲伎倆 2022-06-08 13:54 128阅读 0赞

**数据结构 第5讲 顺序栈**

小张终于攒钱买了车，可是他家住在胡同的尽头，胡同很窄，只能通过一辆车，而且是死胡同，每天小张都为停车发愁，回家早了停在里面，早上上班就要让所有的人挪车，先让胡同口那辆出去，然后挨着一辆一辆出去，小张才能去上班。没办法，小张下班也不敢早回家了，等天黑了别的车都停进去了，再回去把车停在胡同口，这样早上就可以第一个去上班了。就这样，过起了"起早贪黑"的有车生活。

![Center][]

我们看到这个胡同很窄，只能通过一辆车，而且是死胡同，只能从胡同口进出，画图：

![Center 1][]

小汽车是线性排列，而且只能从一端进出，后进的汽车先出去，这就是"栈"，栈也是一种线性表，只不过它是操作受限的线性表，只能在一端操作，后进先出（Last In First Out，LIFO）。

进出的一端称为栈顶（top），另一端称为栈底（base）。栈可以用顺序存储，也可以用链式存储。我们先看顺序存储方式：

![Center 2][]

从上图可以看出，需要两个指针，base指向栈底，top指向栈顶。

**顺序栈的结构体定义：**

![Center 3][]

> 栈定义好了之后，还要先定义个最大的分配空间，顺序结构都是如此，需要预先分配空间，因此可以采用宏定义：
> 
> \#define Maxsize 100 //预先分配空间，这个数值根据实际需要预估确定；
> 
> **注意：**栈只能在一端操作，后进先出，是**人为规定**的，也就是说不允许在中间查找、取值、插入、删除等操作，但顺序栈本身是顺序存储的，有人就想我非要从中间取一个元素，那肯定可以取出来，没有问题，但是这样做，就不是栈了。不按套路出牌啊～～～
> 
> 下面讲解顺序栈的初始化、入栈，出栈，取栈顶元素等操作（元素以int类型为例）。
> 
> 1. 顺序栈初始化

初始化一个空栈：

![Center 4][]

bool InitStack(SqStack &S) //构造一个空栈S
    {
        S.base = new int[Maxsize];//为顺序栈分配一个最大容量为Maxsize的空间
        if (!S.base) //空间分配失败
            return false;
        S.top=S.base; //top初始为base，空栈
        return true;
    }

> 2. 入栈

> 入栈前要判断是否栈满，如果栈已满，则入栈失败，否则将元素放入栈顶，栈顶指针向上移动一个空间（top++）。

*  例如输入1，入栈：

![Center 5][]

*  接着输入2，入栈：

![Center 6][]

bool Push(SqStack &S, int e) // 插入元素e为新的栈顶元素

if (S.top-S.base == Maxsize) //栈满

return false;

\*(S.top++) = e; //元素e压入栈顶，然后栈顶指针加1，等价于\*S.top=e; S.top++;

return true;

> 3. 出栈
> 
> 出栈前要判断是否栈空，如果栈是空的，则出栈失败，否则将栈顶元素暂存给一个变量，栈顶指针向下移动一个空间（top--）。

![Center 7][]

> 栈顶元素所在的位置实际上是S.top-1，因此把该元素取出来，暂存在变量e中，然后S.top指针向下移动一个位置。既然这样干脆先移动，即--S.top，然后再取元素就可以了。
> 
> 例如4出队后：

![Center 8][]

> 注意：因为顺序存储删除一个元素时，并没有销毁该空间，所以4其实还在那个位置，只不过下次再有元素进栈时，就把它覆盖了。相当于该元素已出栈，因为栈的内容是S.base 到S.top-1。

bool Pop(SqStack &S, int &e) //删除S的栈顶元素，暂存在变量e中

if (S.base == S.top) //栈空

return false;

e = \*(--S.top); //栈顶指针减1，将栈顶元素赋给e

return true;

> 4. 取栈顶元素
> 
> 取栈顶元素和出栈不同，取栈顶元素只是把栈顶元素复制一份，而出栈是指栈内不再包含这个元素。

> 例如取栈顶元素\*(S.top-1)，即元素4，取值后S.top的值没有改变，栈内元素的个数也没有改变。

![Center 9][]

int GetTop(SqStack S) //返回S的栈顶元素，栈顶指针不变

if (S.top != S.base) //栈非空

return \*(S.top - 1); //返回栈顶元素的值，栈顶指针不变

else

return -1;

> 顺序栈基本操作完整代码：

> 完整代码：

#include<iostream>
    using namespace std;
    #define Maxsize 100 //预先分配空间，这个数值根据实际需要预估确定；
     
    typedef struct SqStack {
        int *base; //栈底指针
        int *top; //栈顶指针
    }SqStack;
     
    bool InitStack(SqStack &S) //构造一个空栈S
    {
        S.base = new int[Maxsize];//为顺序栈分配一个最大容量为Maxsize的空间
        if (!S.base) //空间分配失败
            return false;
        S.top=S.base; //top初始为base，空栈
        return true;
    }
     
    bool Push(SqStack &S, int e) // 插入元素e为新的栈顶元素
    {
        if (S.top-S.base == Maxsize) //栈满
            return false;
        *(S.top++) = e; //元素e压入栈顶，然后栈顶指针加1，等价于*S.top=e; S.top++;
        return true;
    }
     
    bool Pop(SqStack &S, int &e) //删除S的栈顶元素，暂存在变量e中
    {
        if (S.base == S.top) //栈空
            return false;
        e = *(--S.top); //栈顶指针减1，将栈顶元素赋给e
        return true;
    }
     
    int GetTop(SqStack S) //返回S的栈顶元素，栈顶指针不变
    {
        if (S.top != S.base) //栈非空
            return *(S.top - 1); //返回栈顶元素的值，栈顶指针不变
        else
            return -1;
    }
     
    int main()
    {
        int n,x;
        SqStack S;
        InitStack(S);//初始化一个顺序栈S
        cout <<"请输入元素个数n：" <<endl;
        cin>>n;
        cout <<"请依次输入n个元素，依次入栈：" <<endl;
        while(n--)
       {
            cin>>x; //输入元素
            Push(S, x);
        }
        cout <<"元素依次出栈：" <<endl;
        while(S.top!=S.base)//如果栈不空，则依次出栈
        {
            cout<<GetTop(S)<<"\t";//输出栈顶元素
            Pop(S, x); //栈顶元素出栈
        }
        return 0;
    }

运行结果：

![20170927184400817][]

[Center]: /images/20220608/407be99df95f4a5c85d671a0d195186d.png
[Center 1]: /images/20220608/abfd86d27e2a46a08c946552a3068e71.png
[Center 2]: /images/20220608/98eb348633e34666978f2b22a89c0270.png
[Center 3]: /images/20220608/d454b401db984a0cb24b7ba63e3a2de6.png
[Center 4]: /images/20220608/68a0cac5e4294bce8b638d39ff6c39a8.png
[Center 5]: /images/20220608/001379c2635e4c6a8ebfdaed332c5a3b.png
[Center 6]: /images/20220608/76fcee9905b6487cb2834b3a9151223f.png
[Center 7]: /images/20220608/392eeed71082440bb9d7d96699b3346f.png
[Center 8]: /images/20220608/5ffe18b9910e44f8b6d7334d657272ca.png
[Center 9]: /images/20220608/45e7761225724e338595fe79122b924a.png
[20170927184400817]: /images/20220608/289108c535134d038c72941b15ef6916.png