当前位置：首页 > news >正文

数据结构-c/c++实现栈（详解，栈容量可以动态增长）

news 来源：原创 2024/9/19 6:29:28

一.栈的基本介绍

栈是一种只能够在一端进行插入和删除的顺序表。如下图

空栈：表示不含任何元素的栈

栈顶：表示允许进行插入和删除元素的一端

栈底：表示不允许进行插入和删除元素的一端

即栈是一种后进先出的线性表数据结构

二.栈的常见操作

StackInit：初始化栈

StackDestory：销毁栈

StackPop：删除栈顶元素

StackPush：向栈顶插入元素

StackSize：计算栈中元素并返回

StackEmpty：判断栈是否为空

StackTop：返回栈顶元素

三.各操作代码实现详解

栈结构的描述代码

typedef int DataType;typedef struct Stack
{DataType* a;    //存储栈的数组int Top;        //指向栈顶元素的下标int Size;       //栈元素大小
}ST;

3.1 StackInit

初始化栈只需要对栈中的三个元素依次初始化即可

//初始化栈
void StackInit(ST* st)
{assert(st != nullptr);st->a = nullptr;st->Top = 0;st->Size = 0;
}

3.2 StackDestory

//销毁栈
void StackDestory(ST* st)
{assert(st != nullptr);free(st->a);	//释放数据st->Size = 0;	//将容量和栈顶指针置0st->Top = 0;
}

3.3 StackPop

//删除数据
void StackPop(ST* st)
{assert(st != nullptr);assert(st->Top > 0);//有数据才能删除st->Top--;//直接让Top减少1即可
}

3.4 StackPush

//插入数据
void StackPush(ST* st, DataType x)
{assert(st != nullptr);if (st->Size == st->Top){int newCapacity = st->Size == 0 ? 4 : st->Size * 2;//设置新空间大小，每次增长两倍DataType* tmp = new DataType[newCapacity];for (int i = 0; i < st->Size; i++){tmp[i] = st->a[i];}//C语言方式//DataType* tmp = (DataType*)realloc(st->a, sizeof(DataType) * newCapacity);if (tmp == nullptr){cout << "new error" << endl;exit(-1);}st->a = tmp;st->Size = newCapacity;}st->a[st->Top] = x;st->Top++;
}

3.5 StackSize

//计算栈容量大小
int StackSize(ST* st)
{assert(st != nullptr);assert(st->Top != 0);return st->Top;
}

3.6 StackEmpty

//判断栈是否为空
bool StatkEmpty(ST* st)
{assert(st->a);if (st->Top == 0){return true;}else{return false;}
}

3.7StackTop

//返回栈顶数据
DataType StackTop(ST* st)
{assert(st != nullptr);assert(st->Top > 0);          //栈顶有元素才能返回return st->a[st->Top - 1];    //位置是Top-1的原因是Top从0开始，表示的是栈顶的后一位
}

四.简单测试

测试代码1

#define _CRT_SECURE_NO_WARNINGS 1
#include"stack.h"void test1()
{ST st;StackInit(&st);StackPush(&st, 1);StackPush(&st, 9);StackPush(&st, 4);StackPush(&st, 6);StackPush(&st, -1);while (!StackEmpty(&st)){cout << StackTop(&st) << endl;StackPop(&st);}
}int main()
{test1();
}

运行结果

加入pop

#define _CRT_SECURE_NO_WARNINGS 1
#include"stack.h"void test1()
{ST st;StackInit(&st);StackPush(&st, 1);StackPush(&st, 9);StackPop(&st);StackPush(&st, 4);StackPop(&st);StackPush(&st, 6);StackPush(&st, -1);while (!StackEmpty(&st)){cout << StackTop(&st) << endl;StackPop(&st);}
}int main()
{test1();
}

测试结果