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

01.01.2020Очередь

Мы обсудили эффективную реализацию 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 . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме