数据结构-3.2.栈的顺序存储实现

---

一.顺序栈的定义：top指针指向栈顶元素

1.图解：

2.代码：

#include<stdio.h>
#define MaxSize 10 //定义栈最多存入的元素个数
​
typedef struct
{
    int data[MaxSize]; //静态数组存放栈中元素
    int top; //栈顶指针 
} SqStack; 
​
int main()
{
    SqStack S;//声明一个顺序栈(分配空间)
    //后续操作。。。 
    return 0;
}

3.实例：

栈顶指针为4，因为第五个元素e下标为4。

---

二.初始化栈以及判断栈是否为空：

注：栈顶指针指向栈顶元素

1.图解：

2.代码：

#include<stdio.h>
#define MaxSize 10 //定义栈最多存入的元素个数
​
typedef struct
{
    int data[MaxSize]; //静态数组存放栈中元素
    int top; //栈顶指针 
} SqStack; 
​
//初始化栈
void InitStack(SqStack &S)
{
    S.top=-1; //初始化栈顶指针，由于一开始没有元素，所以指向-1 
} 
​
//判断栈空
bool StackEmpty(SqStack S) //此时只要方法的结果即可，不需要返回S，所以不用& 
{
    if( S.top==-1 )
    {
        return true; //栈空 
    } 
    else
    {
        return false; //不空 
    }
} 
​
int main()
{
    SqStack S;//声明一个顺序栈(分配空间)
    InitStack(S);
    //后续操作。。。 
    return 0;
}

---

三.进栈操作(插入元素)：

1.图解：

2.代码：

#include<stdio.h>
#define MaxSize 10 //定义栈最多存入的元素个数
​
typedef struct
{
    int data[MaxSize]; //静态数组存放栈中元素
    int top; //栈顶指针 
} SqStack; 
​
//新元素入栈
bool Push(SqStack &S,int x)
{
    if( S.top==MaxSize-1 )//因为此时栈是静态数组，有最大存储范围，所以要判断是否栈满 
    {
        return false; //栈满，无法再插入新元素，报错 
    }
    //走到这儿说明栈没满
    S.top = S.top+1; //指针先加1-->腾出位置 
    S.data[S.top] = x; //新元素入栈 
    return true; 
} 
​
int main()
{
    return 0;
}

---

四.出栈操作(删除元素)：

1.图解：

2.代码：

#include<stdio.h>
#define MaxSize 10 //定义栈最多存入的元素个数
​
typedef struct
{
    int data[MaxSize]; //静态数组存放栈中元素
    int top; //栈顶指针 
} SqStack;
​
//出栈操作
bool Pop(SqStack &S,int &x) //x有&，代表出栈操作里操作的x和函数调用者定义的x对应的是同一份数据，而不是复制品 
{
    if( S.top==-1 )
    {
        return false; //栈空，报错 
    }
    //走到这儿说明栈不为空
    x = S.data[S.top]; //栈顶元素先出栈
    S.top = S.top-1; //指针再减1
    return true; 
} 
​
int main()
{
    return 0;
}

---

五.读取栈顶元素的操作：

1.图解：

2.代码：

#include<stdio.h>
#define MaxSize 10 //定义栈最多存入的元素个数
​
typedef struct
{
    int data[MaxSize]; //静态数组存放栈中元素
    int top; //栈顶指针 
} SqStack;
​
//出栈操作
bool Pop(SqStack &S,int &x)
{
    if(S.top==-1)
    {
        return false; //栈空，报错 
    }
    x = S.data[S.top--]; //先出栈，指针再减1
    return true; 
} 
​
//读取栈顶元素
bool GetTop(SqStack S,int &x)
{
    if(S.top==-1)
    {
        return false;//栈空，报错 
    }
    x = S.data[S.top]; //x记录栈顶元素，x就是栈顶元素 
    return true; 
} 
​
int main()
{
    return 0;
}

---

六.另一种设计方式，针对top指针：top指针指向栈顶元素下一个可以插入元素的位置

针对top指针，还有另一种设计方式，可以一开始就让top指针指向0，因此判断栈是否为空只需要判断top是否为0即可：

这种方式top指针指向下一个可以插入元素的位置，因此接下来有数据元素入栈的话，举例如下：

此时如果让一个新的数据元素x入栈时，需要先把x放入top指针指向的位置(此时top指针指向下一个可以插入元素的位置)，再让top指针加一：

此时如果让栈顶元素x出栈时，需要先让top指针减一(此时top指针指向下一个可以插入元素的位置)，再把top指向的数据元素传回去：

顺序栈的缺点可以通过 链式存储的方式来实现栈或者可以在刚开始的时候给栈分配一个比较大的连续的存储空间(但刚开始分配大的存储空间会导致内存资源的浪费)或者共享栈来提高内存空间的利用率 来解决。

---

七.共享栈：

如果往0号栈放入数据元素的话，那么从下往上依次递增；

如果往1号栈放入数据元素的话，那么从上往下依次递减。

逻辑上用了两个栈，但物理上共享着同一片存储空间，这就会提高内存资源的利用率：

共享栈也会被存满，当top0+1 == top1时共享栈就满了：

---

八.总结：

---

原文地址：https://blog.csdn.net/ADCvbV/article/details/142371710

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！