Stack.html

---
title: '栈的介绍'
date: 2016-9-22 11:23:00
tags: ['栈', '数据结构']
---

<p>栈是一种遵循<strong class="jx-tooltip" data-toggle="tooltip" title="Last in First out">后进先出（LIFO）</strong>原则的有序集合。新添加的或者是待删除的元素都保存在栈的末尾，称作栈顶，另一端就叫栈底。在栈里面，新元素都靠近栈顶，旧元素都接近栈底。</p>
<p>在现实生活中也能发现很多栈的例子。例如，一摞书或者是餐厅里堆放的盘子</p>
<p>栈也被用在编程语言的编译器和内存中保存变量、方法调用。</p>
<div class="page-header article-header">栈的创建</div>
<p>我们将创建一个类来表示栈。让我们从基础开始，先声明这个类：</p>
<pre>
function Stack() {
	//各种属性和方法的声明
}
</pre>
<p>首先，我们需要一种数据结构来保存栈里的元素。可以选择数组：</p>
<p><code>var items = [];</code></p>
<p>接下来，要为我们的栈声明一些方法。</p>
<p>根据栈的特性，我们需要一个方法（push）来让元素进栈，一个方法（pop）出栈。</p>
<p><code>push(element)</code>：添加一个（或者多个）新元素到栈顶</p>
<p><code>pop()</code>：移除栈顶的元素，同时返回被移除的元素（被弹出来的元素还有用并不是删除）。</p>
<p>我们要实现的第一个方法就是push。这个方法负责往栈里面添加新元素，有一点很重要：该方法值添加元素到栈顶，也就是栈的末尾。push方法可以这样写：</p>
<p><pre>
this.push = function(element) {
	items.push(element);
}
</pre></p>
<p>因为我们使用javascript中的数组保存栈里面的元素，所以我们可以使用javascript提供的已有的方法进行实现push方法。</p>
<p>接着，我们来实现pop方法。这个方法主要用来移除栈里面的元素。栈准遵循LIFO原则，因此移除的是最后添加进去的元素。因此，我们可以使用javascript的数组的现成的方法pop来移除栈顶的元素。栈的pop方法可以这样写：</p>
<p><pre>
this.pop = function() {
	return items.pop();//一定要把pop出来的元素return回去。
}
</pre></p>
<p>我们用push和pop方法添加和删除栈中元素，这样一来，我们的栈自然就遵从了LIFO原则。</p>
<p>但是，仅仅有这些方法还是不够，我们需要为我们的栈添加一些额外的辅助方法。如果我们想知道栈里最后添加的元素是什么，也就是我们最后往栈里面添加的元素，可以用<strong class="jx-tooltip" data-toggle="tooltip" title="vi. 窥视，偷看">peek</strong>方法。这个方法返回栈顶的元素：</p>
<p><pre>
this.peek = function() {
	return items[items.length - 1];
}
</pre></p>
<p>因为类内部是用数组保存元素的，所以访问数组的最后一个元素可以用<code>length - 1</code></p>
<div>
	<style>
		#stackStage {
			border: 1px solid black;
			display: block;
			margin: auto;
		}
	</style>
	<canvas id="stackStage" width="200" height="250"></canvas>
	<script src="http://code.createjs.com/easeljs-0.7.1.min.js"></script>
	<script>
		var stackStage = new createjs.Stage("stackStage");

		var stack = new createjs.Container;
		stack.x = 50;
		stack.y = 200;
		stackStage.addChild(stack);

		var elements = [];
		for(var i = 0; i < 3; i++) {
			elements[i] = makeElement();
			var num = new createjs.Text(Math.round(Math.random() * 100).toString(), "14px Arial", "#000000");
			var index = new createjs.Text("[" + i + "]", "14px Arial", "#000000");;
			stack.addChild(index);
			stack.addChild(elements[i]);
			stack.addChild(num);
			index.x = 18;
			index.y = i * -50 - 50 + 18;
			num.x = 68;
			num.y = i * -50 - 50 + 18;
			elements[i].x = 50;
			elements[i].y = i * -50 - 50;
		}
		function makeElement() {
			var element = new createjs.Shape;
			element.graphics.beginStroke("#000000").drawRect(0, 0, 50, 50);
			return element;
		}

		var stackTop = new createjs.Text("栈顶", "14px 'Microsoft Yahei'", "#000000");
		stackTop.x = 61;
		stackTop.y = -170;
		var stackBottom = new createjs.Text("栈底", "14px 'Microsoft Yahei'", "#000000");
		stackBottom.x = 105;
		stackBottom.y = -28;
		stack.addChild(stackTop);
		stack.addChild(stackBottom);

		stackStage.update();
	</script>
</div>
<p>在上图中，有一个包含三个元素的栈，因此内部数组的长度就是3.数组中最后一项的位置是2，<code>length - 1(3 - 1)</code>正好是2.</p>
<p>下一个要实现的方法是isEmpty，如果栈为空的话将返回<code>true</code>，否则就返回<code>false</code>：</p>
<p><pre>
this.isEmpty = function() {
	return items.length == 0;
}
</pre></p>
<p>使用isEmpty方法，我们能简单快捷的判断内部数组的长度是否为0.</p>
<p>类似于数组的length属性，我们也能实现栈的length。对于集合，最好用size代替length。因为栈的内部使用数组保存元素，所以能简单的返回栈的长度：</p>
<p><pre>
this.size = function() {
	return items.length;
}
</pre></p>
<p>有一个需要注意的地方，这里的<code>length</code>是数组的属性，而<code>size</code>是栈的方法，调用需要加上<code>()</code>。</p>
<p>最后，我们来实现<code>clear</code>方法。<code>clear</code>方法用来移除栈里所有元素，把栈清空。实现这个方法最简单的方法是：</p>
<p><pre>
this.clear = function() {
	items = [];
}
</pre></p>
<p>我们也可以多次调用pop方法，把数组中的元素全部移除，这样也能实现<code>clear</code>方法。</p>
<p>OK！栈已经实现。通过一个例子来放松一下：为了检查栈里的内容，我们来实现一个辅助方法，叫<code>print</code>。它会把栈里的所有元素都输出到控制台：</p>
<p><pre>
this.print = function() {
	console.log(items.toString());
}
</pre></p>
<p>这样，我们就完整创建了栈。</p>
<p>来看看我为你准备的栈的动画吧。</p>
<div>
	<iframe height='545' scrolling='no' src='http://codepen.io/aizhizhi/embed/ZpYbWW/?height=545&theme-id=dark&default-tab=result&embed-version=2' frameborder='no' allowtransparency='true' allowfullscreen='true' style='width: 100%;'>See the Pen <a href='http://codepen.io/aizhizhi/pen/ZpYbWW/'>Stack</a> by 蒋璇 (<a href='http://codepen.io/aizhizhi'>@aizhizhi</a>) on <a href='http://codepen.io'>CodePen</a>.
	</iframe>
</div>