一.栈的基本介绍
栈是一种只能够在一端进行插入和删除的顺序表。如下图
空栈:表示不含任何元素的栈
栈顶:表示允许进行插入和删除元素的一端
栈底:表示不允许进行插入和删除元素的一端
即栈是一种后进先出的线性表数据结构
二.栈的常见操作
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();
}
测试结果