栈(Stack)
李艳生
湖北师范大学
物理与电子科学学院
2020年春季
栈
图1 书
栈概念
- 一组遵守后进先出(LIFO)的有序集合
- 一个栈包含栈底，栈顶，栈指针
- 添加或删除操作只能在栈顶
- 新元素在栈顶，旧元素在栈底
- 生活实例:一叠盘子
- 计算机实例:函数嵌套调用，浏览器历史记录
栈操作
- 建栈
- 进栈
- 出栈
- 查看栈顶
- 检查栈空
- 清空栈
算法演示
栈实现
- 基于数组的栈
- 基于对象的栈
基于数组建栈
- 创建一个类封装栈
- 利用数组操作实现栈操作
class Stack{
constructor(){
this.items = [];
}
push(element){}
pop(){}
peek(){}
isEmpty(){}
clear(){}
}
进栈
- 进栈只能在栈顶添加元素
- 利用数组push操作实现进栈
push(element){
this.items.push(element);
}
出栈
- 出栈只能在栈顶删除元素
- 利用数组pop操作实现出栈
pop(){
return this.items.pop();
}
查看栈顶元素
- 查看栈顶只获取栈顶元素,不删除
- 利用数组length属性
peek(){
return this.items[this.items.length - 1];
}
检查栈空
- 栈空返回true,不空返回false
- 利用数组length属性
isEmpty(){
return this.items.length === 0;
}
清空栈
- 将栈中所有元素清空
clear(){
this.items = [];
}
栈使用
- 利用new创建栈对象
//建栈
let stack = new Stack();
//判栈空
console.log(stack.isEmpty());
//进栈
stack.push(1);
stack.push(2);
//查看栈顶
console.log(stack.peek());
//出栈
console.log(stack.pop());
//清空栈
stack.clear();
console.log(stack.isEmpty());
基于对象建栈
- 创建一个类封装栈
- 利用对象操作实现栈操作
class Stack{
constructor(){
this.count = 0;
this.items = {};
}
push(element){}
pop(){}
peek(){}
isEmpty(){}
clear(){}
}
进栈
- 进栈只能在栈顶添加元素
- 利用对象键值对操作实现进栈,this.count作为键，插入元素作为值
- 递增count变量
push(element){
this.items[this.count] = element;
this.count++;
}
检查栈空
- 栈空返回true,不空返回false
- 利用变量count
isEmpty(){
return this.count === 0;
}
出栈
- 出栈只能在栈顶删除元素
- 利用变量count操作实现出栈
pop(){
this.count--;
const ret = this.items[this.count];
delete this.items[this.count];
return ret;
}
查看栈顶元素
- 查看栈顶只获取栈顶元素,不删除
- 利用变量count
peek(){
return this.items[this.count - 1];
}
清空栈
- 将栈中所有元素清空
clear(){
this.count = 0;
this.items = {};
}
栈使用
- 利用new创建栈对象
//建栈
let stack = new Stack();
//判栈空
console.log(stack.isEmpty());
//进栈
stack.push(1);
stack.push(2);
//查看栈顶
console.log(stack.peek());
//出栈
console.log(stack.pop());
//清空栈
stack.clear();
console.log(stack.isEmpty());
用栈解决问题
- 将十进制转换成二进制。
function decimalToBinary(decNumber) {
const remStack = new Stack();
let number = decNumber;
let rem;
let binaryString = '';
while (number > 0) {
rem = Math.floor(number % 2);
remStack.push(rem);
number = Math.floor(number / 2);
}
while (!remStack.isEmpty()) {
binaryString += `${remStack.pop()}`;
}
return binaryString;
}
alert(decimalToBinary(10));