# 堆栈

> 堆栈（英语：stack）又称为栈或堆叠，是计算机科学中一种特殊的串列形式的抽象数据类型，其特殊之处在于只能允许在链表或数组的一端（称为堆栈顶端指针，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。另外堆栈也可以用一维数组或链表的形式来完成。堆栈的另外一个相对的操作方式称为队列。
>
> 由于堆栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。

![](http://dunwu.test.upcdn.net/images/data-structure/stack/stack.png)

<!-- TOC depthFrom:2 depthTo:2 -->

- [概念](#概念)
- [应用](#应用)
- [引申和引用](#引申和引用)

<!-- /TOC -->

## 概念

### 特点

堆栈的基本特点：

1. 先入后出，后入先出。
2. 除头尾节点之外，每个元素有一个前驱，一个后继。

### 操作

堆栈数据结构使用两种基本操作：推入（压栈，push）和弹出（弹栈，pop）：

- 推入 - 将数据放入堆栈的顶端（数组形式或串列形式），堆栈顶端 top 指针加一。
- 弹出 - 将顶端数据数据输出（回传），堆栈顶端数据减一。

## 应用

- 回溯
- 递归
- 深度优先搜索

## 引申和引用

- https://zh.wikipedia.org/wiki/堆栈