数据结构——栈（C++ 实现）

目录

���的概念及结构

栈的代码实现

完整的源文件

总结

---

栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。

栈中数据元素遵守后进先出 LIFO (Last In First Out）。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈，出数据也在栈顶。

下面看图片：

栈的实现一般可以使用数组或者链表实现，相对于链表，使用数组实现会更优一些。因为数组在尾上插入删除数据的代价会比较小

栈的代码实现

完整的功能头文件

#pragma oncestruct Stack{int* data;int top;  //栈顶位置int capacity;  //数组的容量};//对栈初始化void StackInit(Stack* ps);//释放内存void StackDestroy(Stack* ps);//插入数据void StackPush(Stack* ps, int x);//删除数据void StackPop(Stack* ps);//输出栈顶的数据int StackTop(Stack* ps);//栈的大小int StackSize(Stack* ps);//栈是否为空bool StackEmpty(Stack* ps);

1、栈的初始化

每创建一个栈都要进行初始化，将栈顶位置初始化为0，栈的容量大小为0

//对栈初始化void StackInit(Stack* ps){assert(ps);ps->data = NULL;ps->capacity = 0;ps->top = 0;}

2、栈的销毁，释放内存

因为我们使用的是动态增长的栈，所以我们会使用到new来申请空间，在程序结束时，自然需要delete释放内存空间

我们也可以使用静态栈，但是静态栈在实际中一般不实用

//释放内存void StackDestroy(Stack* ps){delete []ps->data;ps->data = NULL;ps->top = 0;ps->capacity = 0;}

3、插入数据

在栈顶位置插入数据

//插入数据void StackPush(Stack* ps, int x){    //首先判断栈容量是否充足，如果不充足则需要扩容if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;int* newData = new int[newCapacity];                //扩容后，需要将原来的数据拷贝到新的空间里if (ps->top != 0){for (int i = 0; i top; i++){newData[i] = ps->data[i];}delete[]ps->data;}//也可以使用C语言中的realloc  但是后面释放内存就应该是使用free//int* newData = (int*)realloc(ps->data, sizeof(int) * newCapacity);ps->data = newData;ps->capacity = newCapacity;}    //开始插入数据ps->data[ps->top] = x;ps->top++;}

 4、删除数据

注意：删除数据也是在栈顶删除，栈最重要的就是后进先出！！！

//删除数据void StackPop(Stack* ps){assert(ps);assert(ps->top);ps->top--;}

5、输出栈顶的元素数据

//输出栈顶的数据int StackTop(Stack* ps){assert(ps);assert(!StackEmpty(ps));  //如果Stack中已经没有值了，则断言return ps->data[ps->top - 1];}

6、输出栈的元素个数

//栈的元素个数int StackSize(Stack* ps){return ps->top;}

7、判断栈是否为空

//栈是否为空bool StackEmpty(Stack* ps){return ps->top == 0;}

完整的源文件

#include#include#include"Stack.h"using namespace std;//对栈初始化void StackInit(Stack* ps){assert(ps);ps->data = NULL;ps->capacity = 0;ps->top = 0;}//释放内存void StackDestroy(Stack* ps){delete []ps->data;ps->data = NULL;ps->top = 0;ps->capacity = 0;}//插入数据void StackPush(Stack* ps, int x){    //首先判断栈容量是否充足，如果不充足则需要扩容if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;int* newData = new int[newCapacity];                //扩容后，需要将原来的数据拷贝到新的空间里if (ps->top != 0){for (int i = 0; i top; i++){newData[i] = ps->data[i];}delete[]ps->data;}//也可以使用C语言中的realloc  但是后面释放内存就应该是使用free//int* newData = (int*)realloc(ps->data, sizeof(int) * newCapacity);ps->data = newData;ps->capacity = newCapacity;}    //开始插入数据ps->data[ps->top] = x;ps->top++;}//删除数据void StackPop(Stack* ps){assert(ps);assert(ps->top);ps->top--;}//输出栈顶的数据int StackTop(Stack* ps){assert(ps);assert(!StackEmpty(ps));  //如果Stack中已经没有值了，则断言return ps->data[ps->top - 1];}//栈的元素个数int StackSize(Stack* ps){return ps->top;}//栈是否为空bool StackEmpty(Stack* ps){return ps->top == 0;}

总结

谨记：栈最重要的特点就是后进先出