数组是一个线性结构,并且可以在数组的任意位置插入和删除元素。但是有时候,我们为了实现某些功能,必须对这种任意性加以限制。栈和队列就是比较常见的受限的线性结构。
栈(stack)是一种运算受限的线性表:
LIFO(last in first out)
表示就是后进入的元素,第一个弹出栈空间。类似于自动餐托盘,最后放上的托盘,往往先把拿出去使用。如下图所示:
栈的特点:先进后出,后进先出。
题目:有 6 个元素 6,5,4,3,2,1 按顺序进栈,问下列哪一个不是合法的出栈顺序?
题目所说的按顺序进栈指的不是一次性全部进栈,而是有进有出,进栈顺序为 6 -> 5 -> 4 -> 3 -> 2 -> 1。
解析:
push()
添加一个新元素到栈顶位置。pop()
移除栈顶的元素,同时返回被移除的元素。peek()
返回栈顶的元素,不对栈做任何修改(该方法不会移除栈顶的元素,仅仅返回它)。isEmpty()
如果栈里没有任何元素就返回 true
,否则返回 false
。size()
返回栈里的元素个数。这个方法和数组的 length
属性类似。toString()
将栈结构的内容以字符串的形式返回。// 栈结构的封装
class Map {
constructor() {
this.items = [];
}
// push(item) 压栈操作,往栈里面添加元素
push(item) {
this.items.push(item);
}
// pop() 出栈操作,从栈中取出元素,并返回取出的那个元素
pop() {
return this.items.pop();
}
// peek() 查看栈顶元素
peek() {
return this.items[this.items.length - 1];
}
// isEmpty() 判断栈是否为空
isEmpty() {
return this.items.length === 0;
}
// size() 获取栈中元素个数
size() {
return this.items.length;
}
// toString() 返回以字符串形式的栈内元素数据
toString() {
let result = '';
for (let item of this.items) {
result += item + ' ';
}
return result;
}
}
// push() 测试
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.items); //--> [1, 2, 3]
// pop() 测试
console.log(stack.pop()); //--> 3
// peek() 测试
console.log(stack.peek()); //--> 2
// isEmpty() 测试
console.log(stack.isEmpty()); //--> false
// size() 测试
console.log(stack.size()); //--> 2
// toString() 测试
console.log(stack.toString()); //--> 1 2
利用栈结构的特点封装实现十进制转换为二进制的方法。
function dec2bin(dec) {
// new 一个 Map,保存余数
const stack = new Map();
// 当不确定循环次数时,使用 while 循环
while (dec > 0) {
// 除二取余法
stack.push(dec % 2); // 获取余数,放入栈中
dec = Math.floor(dec / 2); // 除数除以二,向下取整
}
let binaryString = '';
// 不断地从栈中取出元素(0 或 1),并拼接到一起。
while (!stack.isEmpty()) {
binaryString += stack.pop();
}
return binaryString;
}
// dec2bin() 测试
console.log(dec2bin(100)); //--> 1100100
console.log(dec2bin(88)); //--> 1011000
专辑: