Алгоритмы и структуры данных в JS — очередь

внешний интерфейс алгоритм JavaScript модульный тест

Очередь

мы сказали раньшекуча, которая представляет собой относительно эффективную структуру данных, которая следует принципу «первый пришел — последним вышел» (LIFO, «последний пришел — первый ушел»). И сегодня мы собираемся обсудитьочередь, это тоже особый список, он отличается от стека, очередь может вставлять элементы только в конец очереди, удалять элементы в начале очереди, так же, как мы обычно стоим в очереди, чтобы купить билеты~

Очередь используется для хранения данных, организованных по порядку, в соответствии с принципом «первым поступил — первым обслужен» (FIFO, First-In-First-Out), а также представляет собой структуру данных, обычно используемую компьютерами. задачи пула и т.д.

Аналогично стеку, есть две основные операции очереди: вставка новых элементов в очередь и удаление элементов в очереди, то есть операции постановки в очередь и удаления из очереди, мы используем два метода постановки в очередь и удаления из очереди.

Кроме того, очередь имеет некоторые другие операции, такие как чтение элемента в голове очереди, эта операция только возвращает элемент головы и не удаляет его из очереди, аналогично методу просмотра стека; метод возврата считывает элемент в конце очереди; метод toString может печатать все элементы в текущей очереди; метод clear очищает текущую очередь и так далее.

队列数据定义
Определение данных очереди

Определяем тип данных, который можно реализовать через массив в JS.

Реализация очереди

//定义队列

function Queue(){
    this.dataStore = [];
    this.enqueue = enqueue;     //入队
    this.dequeue = dequeue;     //出队
    this.front = front;         //查看队首元素
    this.back = back;           //查看队尾元素
    this.toString = toString;   //显示队列所有元素
    this.clear = clear;         //清空当前队列
    this.empty = empty;         //判断当前队列是否为空
}

Давайте сначала реализуем операцию постановки в очередь:

enqueue: добавить элемент в очередь

//向队列末尾添加一个元素，直接调用 push 方法即可

function enqueue ( element ) {
    this.dataStore.push( element );
}

Поскольку у массива в JS есть преимущества, которых нет в других языках, вы можете напрямую использовать метод сдвига для удаления первого элемента массива, поэтому реализация операции удаления из очереди становится очень простой.

dequeue: удалить элемент в начале очереди

//删除队列首的元素，可以利用 JS 数组中的 shift 方法

function dequeue () {
    if( this.empty() ) return 'This queue is empty';
    else this.dataStore.shift();
}

Мы заметили, что выше я решил проверить, есть ли еще элементы в очереди, потому что бессмысленно удалять элементы пустой очереди, поэтому давайте посмотрим, как реализован пустой метод.

пустой: определить, пуста ли очередь

//我们通过判断 dataStore 的长度就可知道队列是否为空

function empty(){
    if( this.dataStore.length == 0 ) return true;
    else return false;
}

Сначала рассмотрим эти методы.

var queue = new Queue();

console.log( queue.empty() );       //true

//添加几个元素
queue.enqueue('Apple');
queue.enqueue('Banana');
queue.enqueue('Pear');

console.log( queue.empty() );       // false

Теперь, я не знаю, кто первый, а кто последний, мы можем использовать передний и задний методы, чтобы проверить отдельно,

спереди: просмотреть головной элемент команды

//查看队首元素，直接返回数组首个元素即可

function front(){
    if( this.empty() ) return 'This queue is empty';
    else return this.dataStore[0]；
}

назад: просмотр заднего элемента

//查看队首元素，直接返回数组最后一个元素即可

//读取队列尾的元素
function back () {
    if( this.empty() ) return 'This queue is empty';
    else return this.dataStore[ this.dataStore.length - 1 ];
}

Давайте посмотрим, правильно ли это:

//查看队首元素
console.log( queue.front() );  // Apple
//查看队尾元素  
console.log( queue.back() );   // Pear

//出队
queue.dequeue();

//查看队首元素
console.log( queue.front() );  // Banana
//查看队尾元素  
console.log( queue.back() );   // Pear

нет проблем! Теперь я хочу посмотреть, сколько всего фруктов, метод toString для достижения,

toString: просмотреть все элементы в очереди

//查看对了所有元素，我这里采用数组的 join 方法实现

function toString(){
    return this.dataStore.join('\n');
}

Теперь вы можете увидеть, какие фрукты вы еще не ели,

console.log( queue.toString() )     //  Apple
                                    //  Banana
                                    //  Pear

У нас остался четкий метод, если вы съели все фрукты, то вам следует использовать четкий метод,

//清空当前队列，也很简单，我们直接将 dataStore 数值清空即可

function clear(){
    delete this.dataStore;
    this.dataStor = [];
}

До сих пор мы реализовали очередь с помощью JS. Как насчет того, как вы думаете, массив JS очень прост в использовании и избавляет от многих проблем, нет! !

//清空队列

queue.clear();

console.log( queue.empty() );    // true

Затем мы используем очереди для реализации поразрядной сортировки.

Сортировка по основанию (сортировка по основанию) относится к «сортировке с распределением», которая распределяет элементы для сортировки по некоторым «сегментам» с помощью некоторой информации о значении ключа, чтобы добиться эффекта сортировки, метод сортировки по основанию. Это стабильная сортировка. , а его временная сложность O (nlog(r)m), где r — взятая система счисления, а m — количество куч.В некоторых случаях эффективность метода сортировки по основанию выше, чем у других устойчивых сортировок по полу. .

Давайте сначала рассмотрим этапы реализации сортировки по основанию (в качестве примера возьмем две цифры), вам нужно сканировать дважды, первый раз сортируется по одной цифре, второй раз сортируется по десяти цифре, и каждый номер присваивается в соответствии с соответствующее значение Перейдите к разным ящикам и, наконец, выньте номера ящиков по очереди, чтобы сформировать новый список, который представляет собой отсортированные числа.

  1. Предположим, у нас есть строка чисел 73, 22, 93, 43, 55, 14, 28, 65, 39, 81.

  2. Сначала отсортируйте по однозначным числам и поместите их в разные поля, как показано ниже.


    第一次排序
    первый сорт
  3. Затем объедините значения в этих полях, чтобы сформировать следующую последовательность: 81, 22, 73, 93, 43, 14, 55, 65, 28, 39.

  4. Затем отсортируйте по десяти цифрам, а затем поместите их в разные поля, как показано ниже.


    第二次排序
    второго порядка
  5. Далее значения в этих полях снова объединяются, и вся последовательность сортируется: 14, 22, 28, 39, 43, 55, 65, 73, 81, 93.

Мы уже поняли идею алгоритма поразрядной сортировки, а затем нам нужно объединить очередь, чтобы реализовать ее, давайте посмотрим.

//基数排序

var queues = [];    //定义队列数组
var nums = [];      //定义数字数组

//选十个0~99的随机数进行排序
for ( var i = 0 ; i < 10 ; i ++ ){
    queues[i] = new Queue();
    nums[i] = Math.floor( Math.random() * 101 );
}

//排序之前
console.log( 'before radix sort: ' + nums );

//基数排序
distribution( nums , queues , 10 , 1 );
collect( queues , nums );
distribution( nums , queues , 10 , 10 );
collect( queues , nums );

//排序之后
console.info('after radix sort: ' + nums );

//根据相应的（个位和十位）数值，将数字分配到相应队列

function distribution ( nums , queues , n , digit ) {  //digit表示个位或者十位的值
    for( var i = 0 ; i < n ; i++ ){
        if( digit == 1){
            queues[ nums[i] % 10 ].enqueue( nums[i] );
        }else{
            queues[ Math.floor( nums[i] / 10 ) ].enqueue( nums[i] );
        }
    }
}

//从队列中收集数字

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

Я публикую результаты двух наборов тестов здесь, чтобы вы могли попрактиковаться сами.

//第一组测试

before radix sort: 23,39,2,67,90,41,47,21,98,13
after radix sort: 2,13,21,23,39,41,47,67,90,98

//第二组测试

before radix sort: 29,62,38,16,55,26,33,54,76,65
after radix sort: 16,26,29,33,38,54,55,62,65,76

На этом наша очередь подошла к концу, и каждый может расширяться дальше, например, приоритетной очередью, круговой очередью и т. д. Я надеюсь, что каждый сможет разойтись в своем мышлении, больше практиковаться и работать вместе!

Категории