【数据结构】三、栈和队列，2.顺序栈&共享栈（顺序栈的初始化，判空，进栈，出栈，读取栈顶，顺序栈实例），数据结构，顺序栈与共享栈详解，初始化、判空、进栈、出栈、读取栈顶及实例操作指南

温馨提示：这篇文章已超过438天没有更新，请注意相关的内容是否还可用！

摘要：本文介绍了数据结构中栈的相关知识，重点讲解了顺序栈和共享栈。内容包括顺序栈的初始化、判空、进栈、出栈、读取栈顶等基本操作，以及顺序栈实例的演示。通过学习和理解这些内容，读者可以更好地掌握栈的基本原理和应用，为解决实际问题和开发高效程序打下基础。

文章目录

1、顺序栈

* 用顺序存储实现的栈

* 顺序栈的缺点

* 结构体定义

* 初始化

* 判空

* 进栈

* 出栈

* 读取栈顶

* 销毁栈

* C++实例

2、共享栈

* 初始化

* 判满

顺序栈

用顺序存储实现的栈

顺序栈是栈的一种实现方式，采用顺序存储结构。

顺序栈的缺点

栈的大小不可变。

结构体定义

定义顺序栈的结构体，包括静态数组存放栈中元素和栈顶指针。

#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{
    ElemType data[MaxSize]; //静态数组存放栈中元素
    int top; //栈顶指针
} SqStack; //Sq即sequence：顺序的意思

有的顺序栈结构还包括栈的大小stackSize。

初始化

初始化一个空栈，分配内存空间。

void InitStack(SqStack &amp;S) {
 S.top = -1; //初始化栈顶指针，一般指向-1表示空栈
}

初始化有两种方式：一种是栈顶指针top指向栈顶元素，一般存储的是数组的下标。-1表示空栈；另一种是初始化时top指向0号位置，即top=0，此时栈为空，初始化时需要注意选择哪种方式，进栈和出栈操作需要根据初始化方式来进行，初始化完成后可以进行后续操作，如判空、进栈、出栈等，判空操作即判断一个栈是否为空，时间复杂度为O(1)，进栈操作即将新元素插入成为新的栈顶，时间复杂度也为O(1)，出栈操作即弹出栈顶元素，时间复杂度同样为O(1)，读取栈顶元素操作和出栈操作相似，只是不需要移动栈顶指针，销毁顺序栈时，如果是动态分配的内存需要手动释放，如果使用了动态分配内存的方式，则需要在程序结束时手动释放空间，下面是一个简单的C++实例，展示顺序栈的基本操作，在实例中还包括了创建顺序栈、插入元素、获取栈顶元素等操作的实现，在主函数中创建了一个顺序栈并进行了简单的操作演示，注意在实际使用中需要根据具体需求进行代码调整和优化，在使用动态分配内存时需要注意内存的分配和释放以避免内存泄漏等问题，共享栈的实现方式和顺序栈类似但涉及到两个栈的共享空间管理需要特别注意判满操作以避免溢出等问题，由于篇幅限制这里不再赘述共享栈的详细内容您可以参考相关教材或资料了解共享栈的实现和使用方法，希望以上内容对您有所帮助如果您还有其他问题请随时提问我会尽力解答。 判空判空操作即判断一个栈是否为空，若S为空则返回true否则返回false，时间复杂度为O(1)。 进栈进栈操作即将新元素插入成为新的栈顶，时间复杂度为O(1)。 出栈出栈操作即弹出栈顶元素，时间复杂度同样为O(1)。 读取栈顶元素读取栈顶元素操作和出栈操作相似只是不需要移动栈顶指针。#### C++实例下面是一个简单的C++实例展示顺序栈的基本操作： ```cpp #include <iostream> using namespace std; #define MaxSize 10 //定义最大容量 typedef struct{ int data[MaxSize]; //存放数据 int top; //指向当前数据的顶端位置 }SqStack; //初始化 void InitStack(SqStack &S){ S.top = -1; } //判空 bool StackEmpty(SqStack S){ if(S.top == -1) return true; else return false; } //进栈 bool Push(SqStack &S, int value){ if (S.top == MaxSize-1) //判断是否为满 return false; S.top++; //先移动指针再赋值 S.data[S.top] = value; return true; } //出垛 bool Pop(SqStack &S, int &value){ if (StackEmpty(S)) return false; value = S.data[S.top--]; //先出数据再移动指针 return true; } //获取垛顶元素 bool GetTop(SqStack S, int &value){ if (StackEmpty(S)) return false; value = S.data[S.top]; return true; } int main(){ SqStack stack; InitStack(stack); int value = 5; while (value > 0){ Push(stack, value); value--; } int temp =