# 栈(stack)

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

栈的设计有什么实际的使用场景呢?可以想象一下大学上课的时候,我总是最后来到教室,而最先离开教室😁这个时候,我来到教室就可以称为入栈(push),离开就是出栈(pop),老师想知道谁来的最晚,就可以通过peek找到我,并将我赶出教室/(ㄒoㄒ)/~~.

栈可以保证元素存入和取出的顺序是后进先出(last-in first-out, LIFO)的.栈中弹出的元素总是你最后放进去的那个.另外一个非常类似的数据结构是队列，它是一个先进先出(first-in, first-out, FIFO)的结构.

下面用swift来实现一个基本的栈。只需要包装一下数组，将存取功能限制为 pop、push 和 peek 即可.

	public struct Stack<T> {
    //  创建一个数组
	    var array = [T]()
	    //  入栈,将元素插入数组末端
	    mutating func push(_ element: T) -> Void {
	        array.append(element)
	    }
	    //  出栈,将数组的末端元素移除
	    mutating func pop() -> T? {
	        return array.isEmpty ?  nil : array.removeLast()
	    }
	    //  获取栈顶元素
	    func peek() -> T? {
	        return array.last
	    }
	    
}

压栈(push)操作是将新元素压入数组的尾部，而不是头部。在数组的头部插入元素是一个很耗时的操作，它的时间复杂度为 O(n)，因为需要将现有元素往后移位为新元素腾出空间。而在尾部插入元素的时间复杂度为 O(1)；无论数组有多少元素，这个操作所消耗的时间都是一个常量。

每次调用函数或方法，CPU 都会将函数返回地址压入到运行栈中。当这个函数执行结束的时候，CPU 将返回地址从栈中取出，并据此返回到函数被调用的位置。所以，如果不断地调用太多的函数(例如死递归函数)，就会得到一个所谓的“栈溢出(stack overflow)” 错误，因为 CPU 运行栈没有空间了。