第 3 章
1. 棧數(shù)據(jù)結(jié)構(gòu)
棧是一種遵從后進(jìn)先出(LIFO)原則的有序集合芍耘。新添加的或待刪除的元素都保存在棧的同一端,稱作棧頂熄阻,另一端就叫棧底斋竞。在棧里,新元素都靠近棧頂秃殉,舊元素都接近棧底坝初。
1.1 棧的操作
為棧聲明一些方法:
- push(element(s)):添加一個(gè)(或幾個(gè))新元素到棧頂。
- pop() :移除棧頂?shù)脑丶鼐瑫r(shí)返回被移除的元素鳄袍。
- peek() :返回棧頂?shù)脑兀粚?duì)棧做任何修改(這個(gè)方法不會(huì)移除棧頂?shù)脑乩艄В瑑H僅返回它)拗小。
- isEmpty() :如果棧里沒(méi)有任何元素就返回 true ,否則返回 false 樱哼。
- clear() :移除棧里的所有元素哀九。
- size() :返回棧里的元素個(gè)數(shù)。這個(gè)方法和數(shù)組的 length 屬性很類似搅幅。
//創(chuàng)建一個(gè)類來(lái)表示棧
function Stack(){
//各種屬性和方法的聲明
let items = [];//保存棧里的元素
// 向棧添加元素(只添加元素到棧頂阅束,也就是棧的末尾)
this.push = function(element){
items.push(element);
};
// 從棧移除元素(移除最后添加進(jìn)去的元素)
this.pop = function(){
return items.pop();
};
// 查看棧頂元素
this.peek = function(){
return items[items.length-1];
};
// 檢查棧是否為空
this.isEmpty = function(){
return items.length==0;
};
// 返回棧的長(zhǎng)度
this.size = function(){
return items.length;
};
// 移除棧里所有的元素,把棧清空
this.clear = function(){
items = [];
};
// 打印棧元素
this.print = function(){
console.log(items.toString());
};
}
var stack = new Stack();
console.log(stack.isEmpty());//true
stack.push(1);
stack.push(2);
console.log(stack.peek());//2
stack.push(5);
console.log(stack.size());//3
console.log(stack.isEmpty());//false
stack.push(8);
stack.pop();
stack.pop();
console.log(stack.size());//2
stack.print();//1,2
2. ECMAScript 6 和 Stack 類
2.1 用 ES6 語(yǔ)法聲明 Stack 類
class Stack{
constructor(){
this.items = [];
}
push(element){
this.items.push(element);
}
}
創(chuàng)建私有屬性:
- 用ES6的限定作用域 Symbol 實(shí)現(xiàn)類
ES6新增了一種叫作 Symbol 的基本類型茄唐,它是不可變的围俘,可以用作對(duì)象的屬性。
let _items = Symbol();
class Stack{
constructor(){
this[_items] = [];
}
//Stack方法
}
這種方法創(chuàng)建了一個(gè)假的私有屬性琢融,因?yàn)镋S6新增的 Object.getOwnPropertySymbols 方法能夠取到類里面聲明的所有 Symbols 屬性界牡。
let stack = new Stack();
stack.push(1);
stack.push(2);
let objSymbols = Object.getOwnPropertySymbols(stack);
console.log(objSymbols.length);//1
console.log(objSymbols);//[Symbol()]
console.log(objSymbols[0]);//Symbol()
stack[objSymbols[0]].push(5);
stack.print();//1,2,5
- 用ES6的 WeakMap 實(shí)現(xiàn)類
let Stack = (function(){
const items = new WeakMap();
class Stack{
constructor(){
items.set(this,[]);
}
push(element){
let s = items.get(this);
s.push(element);
}
pop(){
let s = items.get(this);
let r = s.pop();
return r;
}
//其他方法
}
return Stack;
})();
從十進(jìn)制到二進(jìn)制
function divideBy2(decNum){
var remStack = new Stack(),
rem,
binaryStr = '';
while(decNum>0){
rem = Math.floor(decNum%2);
remStack.push(rem);
decNum = Math.floor((decNum/2);
}
while(!remStack.isEmpty()){
binaryStr += remStack.pop().toString();
}
return binaryStr;
}
進(jìn)制轉(zhuǎn)換算法
function divideBy2(decNum,base){
var remStack = new Stack(),
rem,
binaryStr = '',
digits = '0123456789ABCDE';
while(decNum > 0){
rem = Math.floor(decNum % base);
remStack.push(rem);
decNum = Math.floor((decNum / base);
}
while(!remStack.isEmpty()){
binaryStr += digits[remStack.pop()];
}
return binaryStr;
}