【数据结构】栈

博主： Richard
发布时间：2019 年 04 月 08 日
861 次浏览
暂无评论
971字数
分类：数据结构与算法

<div class="tip share">请注意，本文编写于 2130 天前，最后修改于 2130 天前，其中某些信息可能已经过时。</div>

今天先来两个简单的数据结构——栈和队列吧。

##栈 (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)的。

栈可以用数组和链表来实现，这里我用链表写了一遍。

###链表实现
```cpp
#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(); }
};

```

最后修改：2019 年 04 月 08 日