数据结构与算法--队列/栈/列表

发表于 | 0 comments | 浏览 次
字数统计: 1,625字 | 阅读时长 ≈ 8分钟

一. 队列

队列只能在队尾插入元素，在对头删除元素。队列是一种先进先出（FIFO，first-in-first-out）的数据结构。

a. 实现队列

原理： 存储数据的底层数据结构为数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Queue {
     constructor(){
         this.dataStore = []; //存储数据
     }
     //入队
     push(element){
        this.dataStore.push(element);
     }
     //出队(会删除对头元素)
     shift(){
         return this.dataStore.shift();
     }
     //获取对头元素(不会删除对头元素)
     front(){
         return this.dataStore[0];
     }
     //获取队尾元素
     back(){
         return this.dataStore[this.dataStore.length - 1];
     }
     //是否为空
     empty(){
         if (this.dataStore.length === 0) {
             return true;
         } else {
             return false;
         }
     }
 }

b. 适合使用队列的场景

  1. 数据排序
    算法：基数排序（0-99）
    a. 第一次按个位上的数字进行排序
b. 第二次按十位上的数字进行排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    /**
      * 基数排序
      * @param {array} nums 要排序的数据数组
      * @param {array} queues 0-9的九个队列
      * @param {number} digit 表示个位或十位上的值
      */
     function distribute(nums, queues, digit){
        for (let i = 0; i < nums.length; i++) {
            if (digit === 1) {
                queues[nums[i]%10].push(nums[i]);
            } else {
                queues[Math.floor(nums[i]/10)].push(nums[i]);
            }
        }
        collect(queues, nums);
     }

     function collect(queues, nums) {
        let i = 0;
        for (let digit = 0; digit < 10; ++digit) {
            while (!queues[digit].empty()) {
                nums[i++] = queues[digit].shift();
            }
        }
     }


     let queues = [];
     for (let i = 0; i < 10; i++) {
        queues[i] = new Queue();
     }
     let nums = [12,45,65,74,19,50, 78, 98, 92];

     distribute(nums, queues, 1); //[50, 12, 92, 74, 45, 65, 78, 98, 19]
     distribute(nums, queues, 10); //[12, 19, 45, 50, 65, 74, 78, 92, 98]

二. 栈

栈是一种高效的数据结构，因为数据只能在栈顶添加或者删除，所以这样的操作很快，而且很容易实现。

栈内的元素只能通过列表的一端访问，这一端称为栈顶。栈被称为一种后入先出（LIFO，last-in-first-out）的数据结构。
由于栈具有后入先出的特点，所以任何不在栈顶的元素都无法访问。

a. 实现栈

原理： 存储数据的底层数据结构为数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Stack {
    constructor(){
        this.dataStore = []; //存储数据
        this.top = 0;  //栈顶位置
    }
    //入栈方法
    push(element){
        this.dataStore[this.top++] = element;
    }
    //出栈方法（会删除栈顶元素）
    pop(){
        return this.dataStore[--this.top];
    }
    //获取栈顶元素（不会删除栈顶元素）
    peek(){
        return this.dataStore[this.top - 1];
    }
    //获取栈的length    
    length(){
        return this.top;
    }
    //清空栈
    clear(){
        this.top = 0;
    }
}

b. 适合使用栈的场景

  1. 数制间的相互转换（只针对基数为2-9的情况）
    算法：

    a. 最高位为n%b，将此位压入栈
b. 使用n/b代替n
c. 重复步骤1和2，只到n等于0，且没有余数
d. 持续将栈内元素弹出，只到栈为空，依次将这些元素排列，便得到转换后数字的字符串形式

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    /**
     * 将指定的数字转换成指定基数进制的值
     * @param {number} number 要转换的数字
     * @param {number} base 基数
     */
    function transformBase(number, base){
        let stack = new Stack();
        do {
            stack.push(number%base);
            number = Math.floor(number /= base);
        } while (number > 0);
        let converted = '';
        while(stack.length() > 0) {
            converted += stack.pop();
        }
        return converted;
    }

  2. 判断一个字符串是否回文
    算法：

    a. 从左向右将字符串的每个字符依次入栈，然后在依次出栈组成一个新的字符串，比较两个字符串是否相等

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    /**
     * 判断str是否为回文
     * @param {string} str 
     */
    function isPalindrome(str) {
        let stack = new Stack();
        for (let i = 0; i < str.length; i++) {
            stack.push(str[i]);
        }
        let newStr = '';
        while (stack.length() > 0) {
            newStr += stack.pop();
        }
        if (newStr === str) {
            return true;
        }else{
            return false;
        }
    }

  3. 模拟递归
    算法：

    a. 将数字依次减一入栈，然后出栈相乘

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    /**
     * 模拟递归
     * @param {number} number 
     */
    function fact(number){
        let stack = new Stack();
        while (number > 1) {
            stack.push(number--);
        }
        let result = 1;
        while(stack.length() > 0){
            result *= stack.pop();
        }
        return result;
    }

三. 列表

列表是一组有序的数据，每个列表中的数据项称为元素。

a. 实现列表

原理： 存储数据的底层数据结构为数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
class List {
    constructor(){
        this.listsize = 0;
        this.pos = 0;
        this.dataStore = [];
        this.hasNext = false;
        this.hasPrev = false;
    }
    //尾部添加元素
    append (element) {
        this.dataStore[this.listsize++] = element;
    }
    //获取指定元素的位置
    find (element) {
        return this.dataStore.indexOf(element);
    }
    //删除指定元素
    remove (element) {
        const foundAt = this.find(element);
        if (foundAt > -1) {
            this.dataStore.splice(foundAt, 1);
            --this.listsize;
            return true;
        }
        return false;
    }
    //通过index删除元素
    removeByIndex (index) {
        if (index > -1) {
            this.dataStore.splice(index, 1);
            --this.listsize;
            return true;
        }
        return false;
    }
    //返回列表length
    length () {
        return this.listsize;
    }
    //在某个元素后面插入一个新元素
    insertAfterByElement (element, afterElement) {
        const index = this.find(afterElement);
        if (index > -1) {
            this.dataStore.splice(index+1, 0, element);
            ++this.listsize;
            return true;
        } 
        return false;
    }
    //在某个元素前面插入一个新元素
    insertBeforeByElement (element, beforeElement) {
        const index = this.find(beforeElement);
        if (index > -1) {
            this.dataStore.splice(index, 0, element);
            ++this.listsize;
            return true;
        } 
        return false;
    }
    //在某个元素后面插入一个新元素通过index
    insertAfterByIndex (index, element) {
        if (index > -1) {
            this.dataStore.splice(index+1, 0, element);
            ++this.listsize;
            return true;
        }
        return false;
    }
    //在某个元素前面插入一个新元素通过index
    insertBeforeByIndex (index, element) {
        if (index > -1) {
            this.dataStore.splice(index, 0, element);
            ++this.listsize;
            return true;
        }
        return false;
    }
    //清除列表
    clear () {
        this.dataStore.length = 0;
        this.listsize = this.pos = 0;
    }
    //列表是否包含指定元素
    contains (element) {
        return this.find(element) > -1 ? true : false;
    }
    //指到列表顶部
    front () {
        this.pos = 0;
    }
    //指到列表尾部
    end () {
        this.pos = this.listsize - 1;
    }
    //当前位置的前一位
    prev () {
        --this.pos;
    }
    //当前位置的后一位
    next () {
        if (this.pos < this.listsize) {
            ++this.pos;
        }
    }
    //当前位置
    currPos () {
        return this.pos;
    }
    //移动到指定位置
    moveTo (position) {
        this.pos = position;
    }
    //得到当前元素
    getCurElement () {
        return this.dataStore[this.pos];
    }
    //通过index得到元素
    getElementByIndex (index) {
        return this.dataStore[index];
    }
    //得到元素位置
    getElementByElement (element) {
        const index = this.find(element);
        return this.getElementByIndex(index);
    }
    //是否有下一位
    hasNext () {
        return this.pos < this.listsize;
    }
    //是否有前一位
    hasPrev () {
        return this.pos > 0;
    }

baishiwen wechat
欢迎您扫一扫上面的微信公众号，订阅我的博客！