一、利用链表实现栈
1、链表实现的思路
由于栈是一种较为简单的数据结构,用链表实现栈,逻辑上和数组差不多。
数组实现栈时,每次入栈就相当于将数组中下一个位置填值
链表则不同,每次入栈相当于在后面多链上一个节点,而出栈则是删除最后一个节点
来看一下动画演示
2、设计栈的结构
根据上面的分析,可以得出,我们需要一下数据
- 容纳数据的链表
- 一个表示栈底的节点,该节点不存放数据
- 一个表示栈顶的指针,为了方便出栈和判断栈空
需要如下功能
由于我们是用链表模拟栈,因此不会有栈满的情况
// 栈的结构
class Stack {
private:
std::list<int> stk;
// 这里的栈顶栈底指针用迭代器代替
std::list<int>::iterator bottom;
std::list<int>::iterator top;
public:
Stack();
void push();
int pop();
bool isEmpty();
};
3、入栈操作
直接利用list
内置的在尾部插入函数,并递增栈顶迭代器
void Stack::push(val) {
stk.emplace_back(val);
++top;
}
4、出栈操作
先判断时候为空,再执行操作
int Stack::pop() {
int temp = INT_MAX;
if (!isEmpty()) {
temp = *top;
stk.erase(top);
// 删除元素之后top迭代器失效,不能递减
top = --stk.end();
} else {
std::cerr << "Stack empty, pop failed!" << std::endl;
}
return temp;
}
5、判断栈空
bool Stack::isEmpty() {
return top == bottom;
}
6、构造析构
Stack::Stack()
: stk({0}), bottom(stk.begin()), top(stk.begin()) { }
// 不涉及动态内存,使用默认析构函数
7、完整代码
// Stack.h 栈定义头文件
#include <list>
// 栈的结构
class Stack {
public:
std::list<int> stk;
// 这里的栈顶栈底指针用迭代器代替
std::list<int>::iterator bottom;
std::list<int>::iterator top;
public:
Stack();
void push(int);
int pop();
inline bool isEmpty() { return top == bottom; }
};
// Stack.cpp 栈的函数实现
#include <iostream>
#include <list>
#include "Stack.h"
Stack::Stack()
: stk({0}), bottom(stk.begin()), top(stk.begin()) { }
// 不涉及动态内存,使用默认析构函数
void Stack::push(int val) {
stk.emplace_back(val);
++top;
}
int Stack::pop() {
int temp = INT_MAX;
if (!isEmpty()) {
temp = *top;
stk.erase(top);
// 删除元素之后top迭代器失效,不能递减
top = --stk.end();
} else {
std::cerr << "Stack empty, pop failed!" << std::endl;
}
return temp;
}
// StackTest.cpp 测试代码
#include <iostream>
#include "Stack.h"
int main(int argc, char* argv[]) {
Stack stack;
// 测试空栈出栈操作
stack.pop();
// 测试入栈操作
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
// 测试出栈操作
for (auto i = 0; i < 4; ++i)
std::cout << stack.pop() << " ";
std::cout << std::endl;
/* 期望输出
* Stack empty, pop failed!
* 4 3 2 1
*/
return 0;
}