一、顺序栈的概念
栈的存储与一般线性表的存储类似,主要分为两种:顺序存储和链式存储。
通过顺序存储方式实现的栈称之为顺序栈。
类似于顺序表的定义,要分配一块连续的存储空间存储栈中的元素,栈底的位置可以固定在数组的任何一端(一般情况下,在下标为0的一端),而栈顶随着插入和删除动态变化,我们可以用一个变量来记录当前栈顶的位置(实际上是栈顶元素的下一个位置),存储结构如下所示:
顺序栈的存储结构:
二、顺序栈的实现
typedef int DataType; // 以整型为栈的数据类型
class SeqStack {
private:
DataType *base; // 栈底指针
DataType *top; // 栈顶指针始终指向栈顶元素的后一个位置
int size; // 栈的大小
public:
SeqStack(int stacksize = 100) { // 构造了一个空栈,默认大小为100个单元
base = new DataType [staticsize];
top = base; // 指向栈顶元素的后一位置
size = stacksize;
}
~SeqStack() { // 销毁一个已存在的栈
delete[] base;
top = NULL;
base = NULL;
}
int Empty_Stack(); // 判断栈是否为空
int Push_Stack(DataType e); // 将元素e插入栈顶
int Pop_Stack(DataType &e); // 从栈顶删除一个元素到e中返回
int GetTop_Stack(DataType &e); // 从栈顶取出一个元素到e中返回
}
(一)判断栈是否为空
算法思想: 判断top是否小于等于base,小于等于则为空栈,返回1,否则返回0。
实现如下:
int SeqStack::Empty_Stack() {
return (top <= base)
}
(二)入栈操作
算法思想:首先判断栈是否已满,若满则失败,返回0;否则,由于栈的top指向栈顶元素的后一个位置,将入栈元素赋到top的位置,再将top+1指向新的位置,成功返回1。
实现如下:
int Push_Stack(DataType e) {
if (top - base < size) { // 判断栈是否为满
*top = e;
top++;
return 1;
} else {
return 0;
}
}
(三)出栈操作
算法思想:首先判断栈是否为空,若空则失败,返回0;否则,由于栈的top指向栈顶元素的后一位置,要先修改top为top-1,在将其所指向的元素以引用参数e返回,成功返回1。
实现如下:
int SeqStack::Pop_Stack(DataType &e) {
if (top > base) { // 判断栈是否为空
top--;
e = *top;
return 1;
} else {
return 0;
}
}
(四)取栈顶元素操作
算法思想:首先判断栈是否为空,若空则失败,返回0;否则,由于栈的top指向栈顶元素的后一位置,返回top-1所指单元的值,栈不发生变化。
实现如下:
int SeqStack::GetTop_Stack(DataType &e) {
if (top > base) { // 判断栈是否为空
e = *(top - 1);
return 1;
} else {
return 0;
}
}