Рубрики

Как эффективно реализовать k очередей в одном массиве?

Мы обсудили эффективную реализацию k стека в массиве . В этом посте обсуждается то же самое для очереди. Ниже приводится подробное изложение проблемы.


Создайте структуру данных kQueues, которая представляет k очередей. Реализация kQueues должна использовать только один массив, т.е. k очереди должны использовать один и тот же массив для хранения элементов. Следующие функции должны поддерживаться kQueues.

enqueue (int x, int qn) -> добавляет x к номеру очереди 'qn', где qn от 0 до k-1
dequeue (int qn) -> удаляет элемент из номера очереди 'qn', где qn от 0 до k-1

Способ 1 (разделить массив на слоты размером н / к)
Простой способ реализации k очередей — разделить массив на k слотов размером n / k каждый и зафиксировать слоты для разных очередей, т. Е. Использовать arr [0] для arr [n / k-1] для первой очереди. и от arr [n / k] до arr [2n / k-1] для queue2, где arr [] — это массив, который будет использоваться для реализации двух очередей, а размер массива равен n.

Проблема с этим методом — неэффективное использование пространства массива. Операция постановки в очередь может привести к переполнению, даже если в arr [] есть свободное место. Например, рассмотрите k как 2 и размер массива n как 6. Позвольте нам ставить 3 элемента в очередь первым и ничего не ставить во вторую очередь. Когда мы поместим 4-й элемент в первую очередь, произойдет переполнение, даже если у нас будет место еще для 3 элементов в массиве.

Метод 2 (Пространственно эффективная реализация)
Идея похожа на запись стека , здесь нам нужно использовать три дополнительных массива. В посте стека нам потребовалось два дополнительных массива, требуется еще один массив, потому что в очередях операции enqueue () и dequeue () выполняются с разных концов.

Ниже приведены три дополнительных массива:
1) front [] : имеет размер k и хранит индексы передних элементов во всех очередях.
2) Rear [] : размер k, в котором хранятся индексы задних элементов во всех очередях.
2) next [] : имеет размер n и хранит индексы следующего элемента для всех элементов в массиве arr [].

Здесь arr [] — фактический массив, в котором хранится k стеков.

Вместе с k очередями также поддерживается стек свободных слотов в arr []. Вершина этого стека хранится в переменной «free».

Все записи в переднем [] инициализируются как -1, чтобы указать, что все очереди пусты. Все записи next [i] инициализируются как i + 1, потому что все слоты изначально свободны и указывают на следующий слот. Вершина свободного стека 'free' инициализируется как 0.

Ниже приводится реализация вышеуказанной идеи на C ++.

C ++

// Программа на C ++ для демонстрации реализации k очередей в одном
// массив во времени и пространстве эффективным способом
#include<iostream>
#include<climits>

using namespace std;

  
// Класс C ++ для представления k очередей в одном массиве размера n

class kQueues

{   

    // Массив размера n для хранения фактического контента для хранения в очереди

    int *arr;

    // Массив размера k для хранения индексов передних элементов очереди

    int *front;   

    // Массив размера k для хранения индексов задних элементов очереди

    int *rear; 

    // Массив размера n для хранения следующей записи во всех очередях

    int *next;  

    int n, k;

    int free; // Хранить начальный индекс свободного списка

public:

    // конструктор для создания k очереди в массиве размера n

    kQueues(int k, int n);

  

    // Утилита для проверки наличия свободного места

    bool isFull()   {  return (free == -1);  }

  

    // Чтобы поставить элемент в очередь с номером 'qn', где qn от 0 до k-1

    void enqueue(int item, int qn);

  

    // Для удаления очереди из номера очереди 'qn', где qn от 0 до k-1

    int dequeue(int qn);

  

    // Проверить, является ли номер очереди 'qn' пустым или нет

    bool isEmpty(int qn)  {  return (front[qn] == -1); }

};

  
// Конструктор для создания k очередей в массиве размером n

kQueues::kQueues(int k1, int n1)

{

    // Инициализируем n и k и выделяем память для всех массивов

    k = k1, n = n1;

    arr = new int[n];

    front = new int[k];

    rear = new int[k];

    next = new int[n];

  

    // Инициализируем все очереди как пустые

    for (int i = 0; i < k; i++)

        front[i] = -1;

  

    // Инициализируем все пробелы как свободные

    free = 0;

    for (int i=0; i<n-1; i++)

        next[i] = i+1;

    next[n-1] = -1;  // -1 используется для обозначения конца свободного списка

}

  
// Чтобы поставить элемент в очередь с номером 'qn', где qn от 0 до k-1

void kQueues::enqueue(int item, int qn)

{

    // Проверка переполнения

    if (isFull())

    {

        cout << "\nQueue Overflow\n";

        return;

    }

  

    int i = free;      // Сохраняем индекс первого свободного слота

  

    // Обновление индекса свободного слота до индекса следующего слота в свободном списке

    free = next[i];

  

    if (isEmpty(qn))

        front[qn] = i;

    else

        next[rear[qn]] = i;

  

    next[i] = -1;

  

    // Обновляем следующий за тылом и затем тыл для номера очереди 'qn'

    rear[qn] = i;

  

    // Поместить элемент в массив

    arr[i] = item;

}

  
// Для удаления очереди из номера очереди 'qn', где qn от 0 до k-1

int kQueues::dequeue(int qn)

{

    // Underflow checkSAS

    if (isEmpty(qn))

    {

         cout << "\nQueue Underflow\n";

         return INT_MAX;

    }

  

    // Найти индекс переднего элемента в номере очереди 'qn'

    int i = front[qn];

  

    front[qn] = next[i];  // Изменить вершину, чтобы сохранить следующую предыдущую вершину

  

    // Прикрепить предыдущий фронт к началу списка свободных

    next[i] = free;

    free = i;

  

    // Возвращаем предыдущий передний элемент

    return arr[i];

}

  
/ * Программа драйвера для тестирования класса kStacks * /

int main()

{

    // Давайте создадим 3 очереди в массиве размером 10

    int k = 3, n = 10;

    kQueues ks(k, n);

  

    // Давайте поместим некоторые элементы в очередь № 2

    ks.enqueue(15, 2);

    ks.enqueue(45, 2);

  

    // Давайте поместим некоторые элементы в очередь № 1

    ks.enqueue(17, 1);

    ks.enqueue(49, 1);

    ks.enqueue(39, 1);

  

    // Давайте поместим некоторые элементы в очередь № 0

    ks.enqueue(11, 0);

    ks.enqueue(9, 0);

    ks.enqueue(7, 0);

  

    cout << "Dequeued element from queue 2 is " << ks.dequeue(2) << endl;

    cout << "Dequeued element from queue 1 is " << ks.dequeue(1) << endl;

    cout << "Dequeued element from queue 0 is " << ks.dequeue(0) << endl;

  

    return 0;

}

Джава

// Java-программа для демонстрации реализации k очередей в одном
// массив во времени и пространстве эффективным способом

public class KQueues {

  

    int k;

    int n;

    int[] arr;

    int[] front;

    int[] rear;

    int[] next;

    int free;

      

    KQueues(int k, int n){

          

        // Инициализируем n и k и выделяем память для всех массивов

        this.k = k;

        this.n = n;

        this.arr = new int[n];

        this.front = new int[k];

        this.rear = new int[k];

        this.next = new int[n];

          

        // Инициализируем все очереди как пустые

        for(int i= 0; i< k; i++) {

            front[i] = rear[i] = -1;

        }

          

        // Инициализируем все пробелы как свободные

        free = 0;

        for(int i= 0; i< n-1; i++) {

            next[i] = i+1;

        }

        next[n-1] = -1;

          

          

    }

      

    public static void main(String[] args) 

    

        // Давайте создадим 3 очереди в массиве размером 10

        int k = 3, n = 10

        KQueues ks=  new KQueues(k, n); 

         

          

        // Давайте поместим некоторые элементы в очередь № 2

        ks.enqueue(15, 2); 

        ks.enqueue(45, 2); 

        

        // Давайте поместим некоторые элементы в очередь № 1

        ks.enqueue(17, 1); 

        ks.enqueue(49, 1); 

        ks.enqueue(39, 1); 

        

        // Давайте поместим некоторые элементы в очередь № 0

        ks.enqueue(11, 0); 

        ks.enqueue(9, 0); 

        ks.enqueue(7, 0); 

          

        System.out.println("Dequeued element from queue 2 is "

                                ks.dequeue(2)); 

        System.out.println("Dequeued element from queue 1 is "

                                ks.dequeue(1)); 

        System.out.println("Dequeued element from queue 0 is "

                                ks.dequeue(0) ); 

        

    

      

    // Проверить, номер очереди 'i' пуст или нет

    private boolean isEmpty(int i) {

        return front[i] == -1;

    }

      

    // Удалить из очереди номер 'i', где i от 0 до k-1

    private boolean isFull(int i) {

        return free == -1;

    }

  

    // Чтобы поставить элемент в очередь с номером j, где j от 0 до k-1

    private void enqueue(int item, int j) {

        if(isFull(j)) {

            System.out.println("queue overflow");

            return;

        }

          

        int nextFree = next[free];

          

        if(isEmpty(j)) {

            rear[j] = front[j] = free;

        }else {

            // Обновляем следующий тыл и затем тыл для номера очереди 'j'

            next[rear[j]] = free;

            rear[j] = free;

        }

        next[free] = -1;

          

        // Поместить элемент в массив

        arr[free] = item;

          

        // Обновление индекса свободного слота до индекса следующего слота в свободном списке

        free = nextFree;

    }

      

    // Удалить из очереди номер 'i', где i от 0 до k-1

    private int dequeue(int i) {

        // Underflow checkSAS

        if(isEmpty(i)) {

            System.out.println("Stack underflow");

            return Integer.MIN_VALUE;

        }

          

        // Найти индекс переднего элемента в очереди с номером «i»

        int frontIndex = front[i];

  

        // Изменить вершину, чтобы сохранить следующую предыдущую вершину

        front[i] = next[frontIndex];

          

        // Прикрепить предыдущий фронт к началу списка свободных

        next[frontIndex] = free; 

        free = frontIndex;

          

        return arr[frontIndex];

    }

      
}


Выход:

Dequeued element from queue 2 is 15
Dequeued element from queue 1 is 17
Dequeued element from queue 0 is 11

Временные сложности enqueue () и dequeue () составляют O (1).

Лучшая часть описанной выше реализации состоит в том, что, если в очереди есть доступный слот, то элемент может быть помещен в очередь в любой из очередей, т. Е. Не теряется место. Этот метод требует дополнительного места. Пространство может не быть проблемой, потому что элементы очереди, как правило, большие, например, очереди сотрудников, студентов и т. Д., Где каждый элемент имеет сотни байтов. Для таких больших очередей используемое дополнительное пространство сравнительно очень мало, поскольку в качестве дополнительного пространства мы используем три целочисленных массива.

Эта статья предоставлена Sachin . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Как эффективно реализовать k очередей в одном массиве?

0.00 (0%) 0 votes