栈（Stack）又称为堆栈、堆叠，它其实有三种含义，适用于不同场合，很容易混淆。这篇文章主要介绍 stack 在数据结构方面的含义。
数据结构栈
Stack 是计算机科学中的一种抽象资料类型，是一种有序集合。
Stack 数据结构与物理堆栈相同，添加项目时，将其添加到顶部（top）；移除项目时，始终从顶部移除。
Stack 操作类型
Stack 非常简单、有效，主要是为了方便访问数据。如果你感觉链表难于理解，那么相对来说 stack 就很容易了。
Stack 只有两个必须实现的操作：
1、push：向栈顶部添加元素
2、pop：从栈顶部移除元素
Stack 只能从同一端添加、移除元素，即先进后出（last in first out，缩写为LIFO），最后添加的元素会最先被移除。
栈在所有编程领域都得到了广泛应用。下面是几个示例：
1、iOS 的导航控制器使用 stack 管理视图控制器的入栈、出栈。
2、在架构层面，内存分配使用栈架构。局部变量的内存也是使用栈管理。
3、搜索和征服算法使用栈促进回溯。例如，从迷宫中查找路线。
Stack 的实现
创建一个 playground，在 Sources 文件夹内创建 Stack.swift 文件，在该文件内添加以下代码：
public struct Stack<Element> {
private var storage: [Element] = []
public init() { }
}
extension Stack: CustomStringConvertible {
public var description: String {
"""
---- top ----
\(storage.map { "\($0)"}.reversed().joined(separator: "\n"))
-------------
"""
}
}这里定义了 Stack 数据存储方式，即数组。使用数组的append(_:)、popLast()存取数据是恒定时间的操作，可以满足栈的后进先出原则。
遵守CustomStringConvertible协议可以让栈内容以可读方式输出。
push、pop 操作
为 Stack 添加以下操作：
public mutating func push(_ element: Element)
{
storage.append(element)
}
@discardableResult
public mutating func pop() -> Element?
{
storage.popLast()
}在 playground page 添加以下代码：
example(of: "Using a stack")
{
var stack = Stack<Int>()
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
print(stack)
if let poppedValue = stack.pop()
{
assert(4 == poppedValue)
print("Popped: \(poppedValue)")
}
}输出如下：
--- Example of Using a stack
---- top ----
4
3
2
1
-------------
Popped: 4
push、pop 操作时间复杂度都是O(1)。
非必须实现操作
还有一些非必须实现，但实现了会让栈方便使用的操作。在Stack.swift中添加以下代码：
public func peek() -> Element? {
storage.last
}
public var isEmpty: Bool {
peek() == nil
}peek()只是查看顶部元素，并不对数据进行操作。
你也许会想要不要实现 Swift 中集合相关协议，但栈就是为了限制可以存取数据的方式，遵守类似Collection的协议会违背这一原则。
有时需将已有的数组转化为 stack，以保证存取顺序。添加以下初始化方法，直接更新内部存储。如下所示：
public init(_ elements: [Element])
{
storage = elements
}在 playground page 添加以下代码：
example(of: "Initializing a stack from an array")
{
let array = ["A", "B", "C", "D"]
var stack = Stack(array)
print(stack)
stack.pop()
}上述代码创建的栈元素都是字符串，输出栈后会 pop 掉顶部元素。
栈实战
stack 可用于解决字符串中的括号 ( ) 是否匹配。当遇到左括号时，push 进入 stack；遇到右括号时，从 stack pop 一个元素。如果最终 stack 刚好为空，则符号匹配；否则，不匹配。
// 查看圆扣号是否匹配
func checkParentheses(_ string: String) -> Bool
{
var stack = Stack<Character>()
for character in string
{
if character == "("
{
// 遇到左括号，添加到栈。
stack.push(character)
}
else if character == ")"
{
if stack.isEmpty
{
// 遇到右括号时，如果栈是空的，则不匹配。
return false
}
else
{
// 不是空的，移除一个元素。
stack.pop()
}
}
}
// 最终，栈是空的，就刚好匹配；否则，不匹配。
return stack.isEmpty
}上述算法的时间复杂度是O(n)，n是字符串长度。由于使用了 Stack 数据结构，它的空间复杂度也是O(n)。
栈要点
栈对搜索树至关重要。例如正在迷宫内找出口，可以先把指定点的可选路线左、中、右都加入到栈中，发现一条路线不可行时，只需将其从栈中pop，继续下一条路线即可。
栈是后进先出的数据结构
虽然 stack 数据结构简单，但也是一种重要的数据结构。
Stack 只有两个必备的操作，push 用于添加数据，pop 用于移除数据。
代码调用栈
stack 第二种含义是调用栈（call stack），表示函数像堆积木一样存放，以实现层层调用。
下面是一段 Java 代码：
class Student
{
int age;
String name;
public Student(int Age, String Name)
{
this.age = Age;
setName(Name);
}
public void setName(String Name)
{
this.name = Name;
}
}
public class Main
{
public static void main(String[] args) {
Student s;
s = new Student(23,"Jonh");
}
}上述代码运行时，首先调用 main 方法，里面生成一个 Student 实例，于是又调用 Student 构造函数；在构造函数内，又调用 setName 方法。
这三次调用像积木一样堆起来，称作调用栈。程序运行时，总是先完成最上层的调用，然后将它的值回到下一层调用，直到完成整个调用栈返回结果。
内存区域栈
stack 的第三种含义是存放数据的一种内存区域。一般，系统会划分出两种不同的内存空间：stack（栈）和heap（堆）。
stack 是有结构的，每个区块按照一定次序存放，明确知道每个区块大小。
heap 是没有结构的，数据任意存放。
内存泄漏的定义
内存泄漏（Memory leak）是在计算机科学中，由于疏忽或错误造成程序未能释放已经不再使用的内存。内存泄漏并非指内存在物理上的消失，而是应用程序分配某段内存后，由于设计错误，导致在释放该段内存之前就失去了对该段内存的控制，从而造成了内存的浪费。
内存泄漏通常情况下只能由获得程序源代码的程序员才能分析出来。
内存泄漏导致的后果
内存泄漏会因为减少可用内存的数量从而降低计算机的性能。最终，在最糟糕的情况下，过多的可用内存被分配掉导致全部或部分设备停止正常工作，或者应用程序崩溃。
内存泄漏带来的后果可能是不严重的，有时甚至能够被常规的手段检测出来。在现代操作系统中，一个应用程序使用的常规内存在程序终止时被释放。这表示一个短暂运行的应用程序中的内存泄漏不会导致严重后果。
在以下情况，内存泄漏导致较严重的后果：
1、程序运行后置之不理，并且随着时间的流逝消耗越来越多的内存（比如服务器上的后台任务，尤其是嵌入式系统中的后台任务，这些任务可能被运行后很多年内都置之不理）；
2、新的内存被频繁地分配，比如当显示电脑游戏或动画视频画面时；
3、程序能够请求即使在程序终止之后也不会被释放的内存（比如共享内存）；
4、泄漏在操作系统内部发生；
5、泄漏在系统关键驱动中发生；
6、内存非常有限，比如在嵌入式系统或便携设备中；
7、当运行于一个程序终止时内存并不自动释放内存的操作系统（比如AmigaOS）之上时。
内存泄漏的案例
C语言
下面是一个C语言的例子，在函数f()中申请了内存却没有释放，导致内存泄漏。当程序不停地重复调用这个有问题的函数f，申请内存函数malloc()最后会在程序没有更多可用存储器可以申请时产生错误（函数输出为NULL）。但是，由于函数malloc()输出的结果没有加以出错处理，因此程序会不停地尝试申请存储器，并且在系统有新的空闲内存时，被该程序占用。注意，malloc()返回NULL的原因不一定是因为前述的没有更多可用存储器可以申请，也可能是逻辑地址空间耗尽，在Linux环境上测试的时候后者更容易发生。
#include <stdio.h>
#include <stdlib.h>
void f(void)
{
void* s;
s = malloc(50); /* 申请内存空间 */
return; /* 内在泄漏 - 参见以下资料 */
/*
* s 指向新分配的堆空间。
* 当此函数返回，离开局部变量s的作用域后将无法得知s的值，
* 分配的内存空间不能被释放。
*
* 如要「修复」这个问题，必须想办法释放分配的堆空间，
* 也可以用alloca(3)代替malloc(3)。
* （注意：alloca(3)既不是ANSI函数也不是POSIX函数）
*/
}
int main(void)
{
/* 该函数是一个死循环函数 */
while (true) f(); /* Malloc函数迟早会由于内存泄漏而返回NULL*/
return 0;
}
C++
以下例子中，存储了整数123的内存空间不能被删除，因为地址丢失了。这些空间已无法再使用。
#include <iostream>
using namespace std;
int main()
{
int *a = new int(123);
cout << *a << endl;
// We should write "delete a;" here
a = new int(456);
cout << *a << endl;
delete a;
return 0;
}
Java
Java中的内存泄露，广义并通俗的说，就是：不再会被使用的对象的内存不能被回收，就是内存泄露。
Java中的内存泄露与C++中的表现有所不同。
在C++中，所有被分配了内存的对象，不再使用后，都必须程序员手动的释放他们。所以，每个类，都会含有一个析构函数，作用就是完成清理工作，如果我们忘记了某些对象的释放，就会造成内存泄露。
但是在Java中，我们不用（也没办法）自己释放内存，无用的对象由GC自动清理，这也极大的简化了我们的编程工作。但，实际有时候一些不再会被使用的对象，在GC看来不能被释放，就会造成内存泄露。
对象都是有生命周期的，有的长，有的短，****如果长生命周期的对象持有短生命周期的引用，就很可能会出现内存泄露。
public class Simple
{
Object object;//这是类中的属性，也是该类中的一个全局变量
public void method1()
{
object = new Object();
//...其他代码
}
}分析：在method1方法中，给类的属性赋了值，也就是在堆中创建一个对象，并将object指向该对象。但是当method1方法执行完之后，该object对象就不再被使用了。且object对象并没有直接被垃圾回收掉，只有等到Simple类创建的对象被释放之后，object才会被垃圾回收掉，所以这就有可能导致内存泄漏，也就是说：object这块内存地址不受程序控制了。
安全的写法：
public class Simple
{
Object object;
public void method1()
{
object = new Object();
//...其他代码
object = null;
}
}从代码中可以看到，当在局部方法中使用完全局变量之后，随即将其释放掉，这样java的GC就会将object对象给回收掉。
内存泄漏的影响
如果一个程序存在内存泄漏并且它的内存使用量稳定增长，通常不会有很快的症状。每个物理系统都有一个较大的内存量，如果内存泄漏没有被中止（比如重启造成泄漏的程序）的话，它迟早会造成问题。
大多数的现代计算机操作系统都有存储在RAM芯片中主内存和存储在次级存储设备如硬盘中的虚拟内存，内存分配是动态的——每个进程根据要求获得相应的内存。访问活跃的页面文件被转移到主内存以提高访问速度；反之，访问不活跃的页面文件被转移到次级存储设备。当一个简单的进程消耗大量的内存时，它通常占用越来越多的主内存，使其他程序转到次级存储设备，使系统的运行效率大大降低。甚至在有内存泄漏的程序终止后，其他程序需要相当长的时间才能切换到主内存，恢复原来的运行效率。
当系统所有的内存全部耗完后（包括主内存和虚拟内存，在嵌入式系统中，仅有主内存），所有申请内存的操作将失败。这通常导致程序试图申请内存来终止自己，或造成分段内存访问错误（segmentation fault）。现在有一些专门为修复这种情况而设计的程序，常用的办法是预留一些内存。值得注意的是，第一个遭遇得不到内存问题的程序有时候并不是有内存泄漏的程序。
一些多任务操作系统有特殊的机制来处理内存耗尽得情况，如随机终止一个进程（可能会终止一些正常的进程），或终止耗用内存最大的进程（很有可能是引起内存泄漏的进程）。另一些操作系统则有内存分配限制，这样可以防止任何一个进程耗用完整个系统的内存。这种设计的缺点是有时候某些进程确实需要较大数量的内存时，如一些处理图像，视频和科学计算的进程，操作系统需要重新配置。
如内存泄漏发生在内核，表示操作系统自身发生了问题。那些没有完善的内存管理的计算机，如嵌入式系统，会因为一个长时间的内存泄漏而崩溃。
一些被公众访问的系统，如网络服务器或路由器很容易被黑客攻击，加入一段攻击代码，而产生内存泄漏。
934