目录
栈的概念及结构
栈的代码实现
完整的源文件
总结
栈的概念及结构
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。
栈中数据元素遵守后进先出 LIFO (Last In First Out)。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈,出数据也在栈顶。
下面看图片:
栈的实现一般可以使用数组或者链表实现,相对于链表,使用数组实现会更优一些。因为数组在尾上插入删除数据的代价会比较小
栈的代码实现
完整的功能头文件
#pragma once struct 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 < ps->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 < ps->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; }
总结
谨记:栈最重要的特点就是后进先出