一、链栈的基本概念
栈也可以用链式存储方式实现。一般链栈用单链表表示,其结点结构与单链表的结构相同。即结点为:
typedef int DataType; // 以整型为栈的数据类型
class StackNode { // 定义链栈的结点
public DataType data;
StackNode *next;
StackNode() {
next = NULL;
}
}
由于栈的删除、插入等操作主要是在栈顶进行,而在链表的表头进行插入和删除操作比较方便。所以,我们把表头作为栈顶。存储结构如下图所示:
栈的链式存储:
二、链栈的实现
class LinkStack {
private:
StackNode *top;
public:
LinkStack() { // 构造一个新的空栈
top = NULL;
}
~LinkStack() { // 栈顶指针赋空表示为空栈
StackNode *p;
while(top) {
p = top;
top = top->next;
delete p;
}
top = NULL;
}
int Empty_Stack(); // 判断栈是否为空
int Push_Stack(DataType e); // 将元素e插入栈顶
int Pop_Stack(DataType &e); // 从栈顶删除一个元素到e中返回
int GetTop_Stack(DataType &e); // 从栈顶取出一个元素到e中返回
}
(一)判断栈是否为空
算法思想:判断top是否为空,为空则为空栈,返回1,否则返回0。
实现如下:
int LinkStack::Empty_Stack() { // 判断链表是否为空
return (!top)
}
(二)入栈操作
算法思想:首先为链栈分配空间,若成功,将入栈元素赋值到申请的链栈结点,并插入栈顶,使其成为栈顶元素,成功返回1;否则失败,返回0。
实现如下:
int LinkStack::Push_Stack(DataType e) { // 链栈入栈操作
StackNode *p = new StackNode; // 申请结点
if(p) { // 申请结点成功
p->data = e;
p->next = top;
top = p; // 修改栈顶指针
return 1;
} else {
return 0;
}
}
(三)出栈操作
算法思想:首先判断链栈是否为空,若非空,则取出栈顶元素,以引用参数e返回,并删除这个结点,成功返回1;否则,失败返回0。
实现如下:
int LinkStack::Pop_Stack(int &e) { // 链栈的出栈操作
StackNode *p;
if (top) {
p = top;
e = p->data;
top = top->data; // 修改栈顶指针
delete p; // 删除结点
return 1;
} else {
return 0;
}
}
(四)取栈顶元素操作
算法思想:首先判断栈是否为空,若非空,则取出栈顶元素,以引用参数e返回,成功返回1;否则,失败返回0。
实现如下:
int LinkStack::GetTop_Stack(DataType &e) { // 链栈取栈顶元素
if (top) {
e = p->data;
return 1;
} else {
return 0;
}
}