请注意,本文编写于 1636 天前,最后修改于 1636 天前,其中某些信息可能已经过时。
今天先来两个简单的数据结构——栈和队列吧。
栈 (Stack)
栈是一种线性结构,与数组相比,栈对应的操作是数组的子集。
它只能从一端添加元素,也只能从一端取出元素(这一端称之为栈顶)。
Stack这种数据结构用途很广泛,在计算机的使用中,大量的运用了栈,比如编译器中的词法分析器、Java虚拟机、软件中的撤销操作(Undo)、浏览器中的回退操作,编译器中的函数调用实现等等。
栈的实现
函数说明
函数 | 说明 | 复杂度 |
---|---|---|
void push(int data) | 向栈中加入元素 | 平均O(1) |
int pop() | 弹出栈顶元素 | 平均O(1) |
int top() | 查看栈顶元素 | O(1) |
int size() | 获取栈中元素个数 | O(1) |
bool empty() | 判断栈是否为空 | O(1) |
push和pop操作在最后面进行,有可能触发resize,但均摊来算是O(1)的。
栈可以用数组和链表来实现,这里我用链表写了一遍。
链表实现
#include <list>
using namespace std;
//我之前写过链表了,所以这里直接用C++里面的list吧
class Stack
{
private:
list<int> value;
public:
/*入栈,出栈*/
void push(int data) { value.push_back(data); }
int pop()
{
int tmp = top();
value.pop_back();
return tmp;
}
/*栈信息*/
int top() { return value.back(); }
int size() { return value.size(); }
bool empty() { return value.empty(); }
};