javascript数据结构——栈

 

  栈是一种高效的数据结构,数据只能在栈顶添加或删除,所以这样操作很快,也很容易实现。栈的使用遍布程序语言实现的方方面面,从表达式求值到处理函数调用。接下来,用JavaScript实现一个栈的数据结构。

定义栈的操作

  栈作为一种特殊的列表,只能从一端来进行访问,就像一摞盘子,放只能放在上面,拿也只能从上面拿,所以栈是一种先入后出的一种数据结构。因为栈的这种特点,栈中任意不在栈顶的元素都无法访问,为了得到栈底的元素,必须把该元素之上的元素拿掉,把栈底的元素暴露在栈顶。栈还可以清空其内所有元素,也可以记录栈内元素的个数。

  综上,我们定义几个操作栈的方法。

  • push()    把元素添加到栈顶
  • pop()     把元素从栈顶删除
  • peek()    返回栈顶的元素
  • clear()    清空栈内元素
  • length()    栈内元素的个数

javascript数据结构——栈

 

栈的实现

  实现栈,底层的数据结构采用数组,以定义栈的构造函数开始;

javascript数据结构——栈
function Stack() {
    this.dataStore = [];         //用来保存栈内元素的数组
    this.top = 0;                   //top用来记录栈顶位置,初始化为0
    this.push = push;
    this.pop = pop;
    this.peek = peek;
    this.clear = clear;
    this.length = length;
}
javascript数据结构——栈

 

 

  接下来实现push(),pop(),peek(),clear()和length()。

  • push()方法是,当向栈顶添加一个新元素时,在数组的记录栈顶的位置的top的位置添加这个值,添加完成top需要加1;
  • pop()正好与push()相反,需要top减1,但同时减1之后返回top位置的值,即已删除元素;
  • peek()直接返回数组top-1位置的元素,即栈顶元素就可以了;
  • clear() 直接把top值赋为0,直接清空栈;
  • length()直接返回top的值,栈顶位置即栈内元素个数

  看代码……

javascript数据结构——栈
function push(element) {
    this.dataStore[this.top++] = element;   // 先在top位置加入元素,之后top加1
}

function pop() {
    return this.dataStore[--this.top];   // top先减1,然后返回top位置的元素
}

function peek() {
    return this.dataStore[this.top - 1];
}

function clear() {
    this.top = 0;
}

function length() {
    return this.top;
} 
javascript数据结构——栈

 

栈的测试

  测试一下刚刚定义的栈。

javascript数据结构——栈
const s = new Stack();
s.push('hello');
s.push('world');
s.push('javascript');
console.log(`栈内元素个数:${s.length()}`);
console.log(`栈顶元素为:${s.peek()}`);
let popped = s.pop();
console.log(`删掉的元素是:${popped}`);
console.log(`现在的栈顶元素是:${s.peek()}`);
s.push('vue');
console.log(`push后的栈顶元素:${s.peek()}`);
s.clear();
console.log(`清空后的长度:${s.length()}`);
s.push('react');
console.log(s.peek());
javascript数据结构——栈

 

  借助node命令行,查看以上代码执行结果。

javascript数据结构——栈

  正是预期的结果。 

 

栈的应用 

  下面把栈这种数据结构应用起来解决一些问题。有一些问题特别适合用栈来解决。比如进制转化。

  可以利用栈将一个数字从一种数制转化成另一种数制,例如数字n转换为以b(b为2~9)进制数。转换算法如下。

  1. 最高位为 n % b,将此位压入栈。

  2. 使用 n/b 代替 n。

  3. 重复步骤 1 和 2,直到 n 等于 0,且没有余数。

  4. 持续将栈内元素弹出,直到栈为空,依次将这些元素排列,就得到转换后数字的字符串形式。 

  下面代码实现该算法。

javascript数据结构——栈
function mulBase(num, base) {
    var s = new Stack();
    do {
        s.push(num % base);
        num = Math.floor(num /= base);
    } while (num > 0);
    var converted = "";
    while (s.length() > 0) {
        converted += s.pop();
    }
    return converted;
}

let num1 = mulBase(125, 5);
let num2 = mulBase(87, 2);

console.log(`125转成5进制:${num1}`);
console.log(`87转成2进制:${num2}`);
javascript数据结构——栈

 输出结果为

javascript数据结构——栈

 

 栈是一种比较简单的数据结构,关于栈的内容就写这么多吧!

 

原文:https://www.cnblogs.com/chengzp/p/stack.html
上一篇:最小栈


下一篇:java 栈的使用