栈是一种线性数据结构,存贮以及查找数据时只能访问栈的一端。即后进先出(LIFO,last in first out)结构。栈的主要操作如下:
- clear()——清空栈
- isEmpty()——判断栈是否为空
- push(el)——将元素el压进栈中
- pop()——弹出栈顶部的元素
- topEl()——获取栈顶部的元素,但不删除该元素
最重要的就是push
和pop
。也是与其他数据结构最不同的地方。栈的实现可以用数组或者链表实现,链表实现代码如下:
//栈的链表实现
#include<list>
#include<cassert>
using namespace std;
template<class T>
class mystack {
public:
mystack(){}
void push(const T& e) {
m_list.push_back(e);
}
void pop() {
m_list.pop_back();
}
T& top() {
return m_list.back();
}
bool empty() {
return m_list.empty();
}
void clear() {
m_list.clear();
}
private:
list<T> m_list;
};