20180720160629_333574.png
栈结构
栈也是一种非常常见的数据结构, 并且在程序中的应用非常广泛.
一. 认识栈结构
我们先来简单认识一下栈结构, 它的特点和应用场景等.
栈结构
-
数组
-
我们知道数组是一种线性结构, 并且可以在数组的任意位置插入和删除数据.
-
但是有时候, 我们为了实现某些功能, 必须对这种任意性加以限制.
-
而栈和队列就是比较常见的受限的线性结构, 我们先来学习栈结构.
-
栈（stack），它是一种运算受限的线性表,后进先出(LIFO)
-
LIFO(last in first out)表示就是后进入的元素, 第一个弹出栈空间. 类似于自动餐托盘, 最后放上的托盘, 往往先把拿出去使用.
-
其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。
-
向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；
-
从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
-
生活中类似于栈的
-
自助餐的托盘, 最新放上去的, 最先被客人拿走使用.
-
收到很多的邮件(实体的), 从上往下依次处理这些邮件. (最新到的邮件, 最先处理)
-
注意: 不允许改变邮件的次序, 比如从最小开始, 或者处于最紧急的邮件, 否则就不再是栈结构了. 而是队列或者优先级队列结构.
-
栈结构的图解
image
-
程序中什么是使用栈实现的呢?
-
学了这么久的编程, 是否听说过, 函数调用栈呢?
-
我们知道函数之间和相互调用: A调用B, B中又调用C, C中又调用D.
-
那样在执行的过程中, 会先将A压入栈, A没有执行完, 所有不会弹出栈.
-
在A执行的过程中调用了B, 会将B压入到栈, 这个时候B在栈顶, A在栈底.
-
如果这个时候B可以执行完, 那么B会弹出栈. 但是B有执行完吗? 没有, 它调用了C.
-
所以C会压栈, 并且在栈顶. 而C调用了D, D会压入到栈顶.
-
所以当前的栈顺序是: 栈顶A->B->C->D栈顶
-
D执行完, 弹出栈. C/B/A依次弹出栈.
-
所以我们有函数调用栈的称呼, 就来自于它们内部的实现机制. (通过栈来实现的)
-
函数调用栈图解:
20180720160543_694168.png
栈面试题
-
面试题目:
image
-
题目答案: C
-
A答案: 65进栈, 5出栈, 4进栈出栈, 3进栈出栈, 6出栈, 21进栈,1出栈, 2出栈
-
B答案: 654进栈, 4出栈, 5出栈, 3进栈出栈, 2进栈出栈, 1进栈出栈, 6出栈
-
D答案: 65432进栈, 2出栈, 3出栈, 4出栈, 1进栈出栈, 5出栈, 6出栈
[图片上传失败...(image-7d4958-1535622282498)]
二. 栈结构实现
我们来实现一个类, 用于模拟栈中的操作.
栈的创建
-
我们先来创建一个栈的类, 用于封装栈相关的操作
-
// 栈类
-
function Stack() {
-
// 栈中的属性
-
var items = []
-
// 栈相关的方法
-
}
-
代码解析:
-
我们创建了一个Stack构造函数, 用户创建栈的类.
-
在构造函数中, 定义了一个变量, 这个变量可以用于保存当前栈对象中所有的元素.
-
这个变量是一个数组类型. 我们之后无论是压栈操作还是出栈操作, 都是从数组中添加和删除元素.
-
栈有一些相关的操作方法, 通常无论是什么语言, 操作都是比较类似的.
栈的操作
-
栈常见有哪些操作呢?
-
push(element): 添加一个新元素到栈顶位置.
-
pop()：移除栈顶的元素，同时返回被移除的元素。
-
peek()：返回栈顶的元素，不对栈做任何修改（这个方法不会移除栈顶的元素，仅仅返回它）。
-
isEmpty()：如果栈里没有任何元素就返回true，否则返回false。
-
clear()：移除栈里的所有元素。
-
size()：返回栈里的元素个数。这个方法和数组的length属性很类似。
-
现在我们来实现这些方法:
-
push方法
-
注意: 我们的实现是将最新的元素放在了数组的末尾, 那么数组末尾的元素就是我们的栈顶元素
-
// 压栈操作
-
this.push = function (element) {
-
items.push(element)
-
}
-
pop方法
-
注意: 出栈操作应该是将栈顶的元素删除, 并且返回.
-
因此, 我们这里直接从数组中删除最后一个元素, 并且将该元素返回就可以了
-
// 出栈操作
-
this.pop = function (element) {
-
return items.pop()
-
}
-
peek方法
-
peek方法是一个比较常见的方法, 主要目的是看一眼栈顶的元素.
-
注意: 和pop不同, peek仅仅的瞥一眼栈顶的元素, 并不需要将这个元素从栈顶弹出.
-
// peek操作
-
this.peek = function () {
-
return items[items.length - 1]
-
}
-
isEmpty方法
-
isEmpty方法用户判断栈中是否有元素.
-
实现起来非常简单, 直接判断数组中的元素个数是为0, 为0返回true, 否则返回false
-
// 判断栈中的元素是否为空
-
this.isEmpty = function () {
-
return items.length == 0
-
}
-
size方法
-
size方法是获取栈中元素的个数.
-
因为我们使用的是数组来作为栈的底层实现的, 所以直接获取数组的长度即可.(也可以使用链表作为栈的顶层实现)
-
// 获取栈中元素的个数
-
this.size = function () {
-
return items.length
-
}
完整代码
-
下面我们给出自定义栈的完整代码:
-
注意: 这里我们为了将属性方法放在一起, 没有使用原型来封装方法.
-
// 栈类
-
function Stack() {
-
// 栈中的属性
-
var items = []
-
// 栈相关的方法
-
// 压栈操作
-
this.push = function (element) {
-
items.push(element)
-
}
-
// 出栈操作
-
this.pop = function () {
-
return items.pop()
-
}
-
// peek操作
-
this.peek = function () {
-
return items[items.length - 1]
-
}
-
// 判断栈中的元素是否为空
-
this.isEmpty = function () {
-
return items.length == 0
-
}
-
// 获取栈中元素的个数
-
this.size = function () {
-
return items.length
-
}
-
}
栈的使用
-
我们来使用封装的栈, 模拟刚才的面试题
-
我们做了一下A, 其他大家可以自己练习一下.
-
C是无法使用栈来模拟的, 因为不正确的是C
-
// 模拟面试题
-
var stack = new Stack()
-
// 情况下代码模拟
-
stack.push(6)
-
stack.push(5)
-
stack.pop() // 5
-
stack.push(4)
-
stack.pop() // 4
-
stack.push(3)
-
stack.pop() // 3
-
stack.pop() // 6
-
stack.push(2)
-
stack.push(1)
-
stack.pop() // 1
-
stack.pop() // 2
三. 栈结构应用
我们已经学会了如何使用Stack类，现在就用它解决一些计算机科学中的问题。
十进制转二进制
-
为什么需要十进制转二进制?
-
现实生活中，我们主要使用十进制。
-
但在计算科学中，二进制非常重要，因为计算机里的所有内容都是用二进制数字表示的（0和1）。
-
没有十进制和二进制相互转化的能力，与计算机交流就很困难。
-
如何实现十进制转二进制?
-
要把十进制转化成二进制，我们可以将该十进制数字和2整除（二进制是满二进一），直到结果是0为止。
-
举个例子，把十进制的数字10转化成二进制的数字，过程大概是这样：
image
-
如果我们希望使用代码来实现这个功能呢?
-
// 封装十进制转二进制的函数
-
function dec2bin(decNumer) {
-
// 定义变量
-
var stack = new Stack()
-
var remainder;
-
// 循环除法
-
while (decNumer > 0) {
-
remainder = decNumer % 2
-
decNumer = Math.floor(decNumer / 2)
-
stack.push(remainder)
-
}
-
// 将数据取出
-
var binayriStrng = ""
-
while (!stack.isEmpty()) {
-
binayriStrng += stack.pop()
-
}
-
return binayriStrng
-
}
-
测试代码:
-
// 测试函数
-
alert(dec2bin(10))
-
alert(dec2bin(233))
-
alert(dec2bin(1000))
网友评论