一、什么是栈结构
1、栈是一种非常常见的数据结构,应用十分广泛
- 数组是一种线性结构,可以在任意位置添加和删除元素
- 栈和队列则是一种受限的线性结构,没有数组的任意性
2、结构示意图
栈结构只能从一端(栈顶)添加和删除元素,遵从后进先出的原则
二、栈的应用
函数调用栈
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依次弹出栈.
所以我们有函数调用栈的称呼, 就来自于它们内部的实现机制(通过栈来实现的)
三、栈结构面试题
题目:6个元素6、5、4、3、2、1顺序进栈(不是一次性进栈),哪个是不合法的出栈序列(C)
- A、5、4、3、6、1、2
- B、4、5、3、2、1、6
- C、3、4、6、5、2、1
- D、2、3、4、1、5、6
四、栈的常见操作
push(element)
: 添加一个新元素到栈顶位置.
pop()
:移除栈顶的元素,同时返回被移除的元素。
peek()
:返回栈顶的元素,不对栈做任何修改(这个方法不会移除栈顶的元素,仅仅返回它)。
isEmpty()
:如果栈里没有任何元素就返回true
,否则返回false
。
clear()
:移除栈里的所有元素。
size()
:返回栈里的元素个数。这个方法和数组的length
属性很类似。
toString()
:将栈结构内容以字符串形式返回
五、栈结构的实现
实现栈结构有两种是实现方式:
- 基于数组实现
- 基于链表实现
// 封装一个栈类
function Stack() {
// 栈中的属性
this.items = []
/**
* 相关操作
*/
// 1、压栈
Stack.prototype.push = function (element) {
this.items.push(element)
}
// 2、弹栈
Stack.prototype.pop = function () {
return this.items.pop()
}
// 3、查看栈顶元素
Stack.prototype.peek = function () {
return this.items[this.items.length - 1]
}
// 4、判断栈是否为空
Stack.prototype.isEmpty = function () {
return this.items.length == 0
}
// 5、获取栈元素的个数
Stack.prototype.size = function () {
return this.items.length
}
// 6、toString()方法
Stack.prototype.toString = function () {
let str = ''
for (let i = 0; i < this.items.length; i++) {
str += this.items[i] + ' '
}
return str
}
}
// 使用
let s = new Stack()
s.push(20)
s.push(10)
s.push(100)
s.push(4)
console.log(s) // Stack { items: [ 20, 10, 100, 4 ] }
s.pop()
console.log(s) // Stack { items: [ 20, 10, 100 ] }
console.log(s.size()) // 3
console.log(s.isEmpty()) // false
console.log(s.toString()) // 20 10 100
六、栈的应用
实现十进制转二进制(使用上述封装的栈方法)
// 封装一个十进制转二进制的方法
function decTobin(decNumber) {
// 定义一个栈对象保存过程中的余数
let stack = new Stack()
// 循环操作
while (decNumber > 0) {
// 获取余数存入栈中
stack.push(decNumber % 2)
// 获取整除结果作为下次求余的数字
decNumber = Math.floor(decNumber / 2)
}
// 从栈中取出余数就是二进制结果
let binsryString = ''
while (!stack.isEmpty()) {
binsryString += stack.pop()
}
return binsryString
}
console.log(decTobin(100)) // 1100100
console.log(decTobin(10)) // 1010
console.log(decTobin(1000)) // 1111101000
文章评论