栈

TIP

栈（stack），是一种受限的线性结构，特点是先进后出，后进先出（LIFO：last in first out）

基本特点

• 受限表现：仅允许一端插入和删除，这端称为栈顶，另一端称为栈底
• LIFO：最后进入的元素，最先弹出栈空间，类似自动餐托盘，最后放上去最先被拿走
• 插入元素称为：进栈、入栈、压栈，它是把新元素放到栈顶元素上面，使之成为新的栈顶元素
• 删除元素称为：出栈、退栈，他是把栈顶元素删除掉，使其相邻的元素称为新的栈顶元素

结构图例

常用操作

• push(element)：添加一个新元素到栈顶位置
• pop()：移除栈顶的元素，同时返回被移除的元素
• peek()：返回栈顶的元素，不对栈做任何修改（该方法不会移除栈顶的元素，仅仅返回它）
• isEmpty()：如果栈里没有任何元素就返回 true，否则返回 false
• size()：返回栈里的元素个数。这个方法和数组的 length 属性类似
• toString()：将栈结构的内容以字符串的形式返回

代码实现

// 栈类
function Stack() {
	// 栈中的属性
	this.items = []

	/* 栈相关的方法 */
	// 1.push(): 压栈操作
	Stack.prototype.push = function(element) {
		this.items.push(element)
	}

	// 2.pop()：从栈中取出元素
	Stack.prototype.pop = function() {
		return this.items.pop()
	}

	// 3.peek()：返回栈顶元素
	Stack.prototype.peek = function() {
		return this.items[this.items.length - 1]
	}

	// 4.isEmpty()：判断栈中的元素是否为空
	Stack.prototype.isEmpty = function() {
		return this.items.length == 0
	}

	// 5.size()：获取栈中元素的个数
	Stack.prototype.size = function() {
		return this.items.length
	}

	// 6.toString()：以字符串形式输出栈内数据
	Stack.prototype.toString = function() {
		let resultString = ""
		for (let i = 0; i < this.items.length; i++) {
			resultString += this.items[i] + " "
		}
		return resultString
	}
}

// 模拟面试题
var stack = new Stack()

stack.push(6)
stack.push(5)
stack.push(4)
stack.push(3)

console.log(stack.pop()) // 3
console.log(stack.peek()) // 4
console.log(stack.isEmpty()) // false
console.log(stack.size()) // 3
console.log(stack.toString()) // 6 5 4

程序应用

函数调用栈

A(B(C(D())))

调用顺序：A调用B，B调用C，C调用D
入栈过程：A执行入栈，B执行入栈，C执行入栈，D执行入栈，顺序为：A(栈底) 》 B 》 C 》 D(栈顶)
出栈过程：D执行完了弹出栈，立刻释放D，然后执行C，B，A，顺序为：D 》 C 》 B 》 A

递归

自己调用自己

栈溢出：没有停止条件的递归，会不停把相同的函数压入栈，而没有出栈，最后导致栈溢出(Stack Overfloat)。