如何用C++实现一个顺序栈
- 数据结构 -- 栈的简介
- 顺序栈 - 结构体的定义
- 顺序栈的初始化
- 顺序栈的销毁
- 入栈
- 出栈
- 获取栈顶元素
- 判断顺序栈是否为空
- 返回顺序栈中元素的个数
数据结构 – 栈的简介
- 栈是插入和删除遵循先进后出原则的一种容器。 也是一种线性表
- 对象存放在栈, 可以在任意时间插入栈; 但是在任何时间只有栈顶元素才可以被删除
- 栈的插入和删除都在同一端进行
- 栈分为顺序栈和链栈两种
- 顺序栈 : 以顺序表的形式实现
- 链栈 : 以节点组合的链表形式实现
- 对于数据结构 - 栈, 一般需要以下几种要素:
- 指针域 : 顺序栈指针指向顺序表, 链栈指针指向头节点
- 栈的容量 : 记录栈的容量
- 栈顶指针 : 用于入栈 , 出栈 , 获取栈顶元素等, 甚至记录栈中元素总个数
顺序栈 - 结构体的定义
typedef int STDataType;
typedef struct Stack
{STDataType* arr; int capacity; int top;
}ST;
顺序栈的初始化
void STInit(ST* ps)
{assert(ps); ps->arr = NULL;ps->capacity = 0;ps->top = 0;
}
顺序栈的销毁
void STDestroy(ST* ps)
{assert(ps);assert(ps->arr); delete[] ps->arr;ps->capacity = ps->top = 0;
}
入栈
void STPush(ST* ps, STDataType val)
{assert(ps);if (!ps->arr) {ps->arr = new STDataType[4];ps->capacity = 4;ps->arr[ps->top++] = val;return;}if (ps->top == ps->capacity) {STDataType* newArr = new STDataType[ps->capacity * 2];for (int i = 0; i <= ps->top; i++){newArr[i] = ps->arr[i];}delete[] ps->arr;ps->arr = newArr;ps->capacity *= 2;ps->arr[ps->top++] = val;return;}if (!ps->arr){perror("new failed");exit(-1);}ps->arr[ps->top++] = val;
}
出栈
void STPop(ST* ps)
{assert(ps);assert(ps->top);--ps->top;
}
获取栈顶元素
STDataType STTop(ST* ps)
{assert(ps);assert(ps->top);return ps->arr[ps->top - 1];
}
判断顺序栈是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
返回顺序栈中元素的个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}