本文共 3982 字,大约阅读时间需要 13 分钟。
如需转载, 请咨询作者, 并且注明出处.
有任何问题, 可以关注我的微博: , 或者添加我的微信: 372623326
栈也是一种非常常见的数据结构, 并且在程序中的应用非常广泛.
我们先来简单认识一下栈结构, 它的特点和应用场景等.
栈结构
数组
栈(stack),它是一种运算受限的线性表,后进先出(LIFO)
生活中类似于栈的
栈结构的图解
img
程序中什么是使用栈实现的呢?
函数调用栈图解:
img
栈面试题
面试题目:
img
题目答案: C
我们来实现一个类, 用于模拟栈中的操作.
栈的创建
我们先来创建一个栈的类, 用于封装栈相关的操作
// 栈类function Stack() { // 栈中的属性 var items = [] // 栈相关的方法}
代码解析:
栈的操作
栈常见有哪些操作呢?
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操作this.peek = function () { return items[items.length - 1]}
isEmpty方法
// 判断栈中的元素是否为空this.isEmpty = function () { return items.length == 0}
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 }}
栈的使用
我们来使用封装的栈, 模拟刚才的面试题
// 模拟面试题var stack = new Stack()// 情况下代码模拟stack.push(6)stack.push(5)stack.pop() // 5stack.push(4)stack.pop() // 4stack.push(3)stack.pop() // 3stack.pop() // 6stack.push(2)stack.push(1)stack.pop() // 1stack.pop() // 2
我们已经学会了如何使用
Stack
类,现在就用它解决一些计算机科学中的问题。
十进制转二进制
为什么需要十进制转二进制?
如何实现十进制转二进制?
要把十进制转化成二进制,我们可以将该十进制数字和2整除(二进制是满二进一),直到结果是0为止。
举个例子,把十进制的数字10转化成二进制的数字,过程大概是这样:
img
如果我们希望使用代码来实现这个功能呢?
// 封装十进制转二进制的函数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(dec2bi