目录
栈的概念及结构
栈的代码实现
完整的源文件
总结
栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
栈中数据元素遵守后进先出 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;
}
总结
谨记：栈最重要的特点就是后进先出
好文推荐
发表评论