Hemos discutido la implementación eficiente de k stack en una array . En esta publicación, se discute lo mismo para la cola. A continuación se presenta el enunciado detallado del problema.
Cree una estructura de datos kQueues que represente k colas. La implementación de kQueues debe usar solo una array, es decir, k colas debe usar la misma array para almacenar elementos. Las siguientes funciones deben ser compatibles con kQueues.
- enqueue(int x, int qn) -> agrega x al número de cola ‘qn’ donde qn es de 0 a k-1
- dequeue(int qn) –> elimina un elemento del número de cola ‘qn’ donde qn es de 0 a k-1
Método 1 (Divida la array en ranuras de tamaño n/k):
Una forma simple de implementar k colas es dividir la array en k ranuras de tamaño n/k cada una, y arreglar las ranuras para diferentes colas, es decir, usar arr[0] a arr[n/k-1] para la primera cola , y arr[n/k] a arr[2n/k-1] para queue2 donde arr[] es la array que se usará para implementar dos colas y el tamaño de la array será n.
El problema con este método es un uso ineficiente del espacio de la array. Una operación de puesta en cola puede resultar en un desbordamiento incluso si hay espacio disponible en arr[]. Por ejemplo, considere k como 2 y el tamaño de array n como 6. Pongamos en cola 3 elementos al primero y no pongamos nada en cola en la segunda cola. Cuando ponemos en cola el cuarto elemento en la primera cola, habrá un desbordamiento incluso si tenemos espacio para 3 elementos más en la array.
Método 2 (una implementación eficiente en el espacio):
La idea es similar a la publicación de la pila , aquí necesitamos usar tres arrays adicionales. En la publicación de la pila, necesitábamos dos arrays adicionales, se requiere una array más porque en las colas, las operaciones enqueue() y dequeue() se realizan en diferentes extremos.
Las siguientes son las tres arrays adicionales que se utilizan:
- front[] : este es de tamaño k y almacena índices de elementos frontales en todas las colas.
- rear[] : Esto es de tamaño k y almacena índices de elementos traseros en todas las colas.
- next[] : Esto es de tamaño n y almacena índices del siguiente elemento para todos los elementos en la array arr[].
Aquí arr[] es la array real que almacena k pilas.
Junto con k colas, también se mantiene una pila de espacios libres en arr[]. La parte superior de esta pila se almacena en una variable ‘libre’.
Todas las entradas delante de [] se inicializan como -1 para indicar que todas las colas están vacías. Todas las entradas next[i] se inicializan como i+1 porque todas las ranuras están libres inicialmente y apuntan a la siguiente ranura. En la parte superior de la pila libre, ‘gratis’ se inicializa como 0.
A continuación se muestra la implementación en C++ de la idea anterior.
C++
// A C++ program to demonstrate implementation
// of k queues in a single
// array in time and space efficient way
#include<iostream>
#include<climits>
using namespace std;
// A C++ class to represent k queues
// in a single array of size n
class kQueues
{
// Array of size n to store actual
// content to be stored in queue
int *arr;
// Array of size k to store indexes
// of front elements of the queue
int *front;
// Array of size k to store indexes
// of rear elements of queue
int *rear;
// Array of size n to store next
// entry in all queues
int *next;
int n, k;
int free; // To store the beginning index of the free list
public:
//constructor to create k queue
// in an array of size n
kQueues(int k, int n);
// A utility function to check if
// there is space available
bool isFull() { return (free == -1); }
// To enqueue an item in queue number
// 'qn' where qn is from 0 to k-1
void enqueue(int item, int qn);
// To dequeue an from queue number
// 'qn' where qn is from 0 to k-1
int dequeue(int qn);
// To check whether queue number
// 'qn' is empty or not
bool isEmpty(int qn) { return (front[qn] == -1); }
};
// Constructor to create k queues
// in an array of size n
kQueues::kQueues(int k1, int n1)
{
// Initialize n and k, and allocate
// memory for all arrays
k = k1, n = n1;
arr = new int[n];
front = new int[k];
rear = new int[k];
next = new int[n];
// Initialize all queues as empty
for (int i = 0; i < k; i++)
front[i] = -1;
// Initialize all spaces as free
free = 0;
for (int i=0; i<n-1; i++)
next[i] = i+1;
next[n-1] = -1; // -1 is used to indicate end of free list
}
// To enqueue an item in queue number
// 'qn' where qn is from 0 to k-1
void kQueues::enqueue(int item, int qn)
{
// Overflow check
if (isFull())
{
cout << "\nQueue Overflow\n";
return;
}
int i = free; // Store index of first free slot
// Update index of free slot to index of next slot in free list
free = next[i];
if (isEmpty(qn))
front[qn] = i;
else
next[rear[qn]] = i;
next[i] = -1;
// Update next of rear and then rear for queue number 'qn'
rear[qn] = i;
// Put the item in array
arr[i] = item;
}
// To dequeue an from queue number 'qn' where qn is from 0 to k-1
int kQueues::dequeue(int qn)
{
// Underflow checkSAS
if (isEmpty(qn))
{
cout << "\nQueue Underflow\n";
return INT_MAX;
}
// Find index of front item in queue number 'qn'
int i = front[qn];
// Change top to store next of previous top
front[qn] = next[i];
// Attach the previous front to the
// beginning of free list
next[i] = free;
free = i;
// Return the previous front item
return arr[i];
}
/* Driver program to test kStacks class */
int main()
{
// Let us create 3 queue in an array of size 10
int k = 3, n = 10;
kQueues ks(k, n);
// Let us put some items in queue number 2
ks.enqueue(15, 2);
ks.enqueue(45, 2);
// Let us put some items in queue number 1
ks.enqueue(17, 1);
ks.enqueue(49, 1);
ks.enqueue(39, 1);
// Let us put some items in queue number 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
// A Java program to demonstrate implementation of k queues in a single
// array in time and space efficient way
public class KQueues {
int k;
int n;
int[] arr;
int[] front;
int[] rear;
int[] next;
int free;
KQueues(int k, int n){
// Initialize n and k, and allocate memory for all arrays
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];
// Initialize all queues as empty
for(int i= 0; i< k; i++) {
front[i] = rear[i] = -1;
}
// Initialize all spaces as free
free = 0;
for(int i= 0; i< n-1; i++) {
next[i] = i+1;
}
next[n-1] = -1;
}
public static void main(String[] args)
{
// Let us create 3 queue in an array of size 10
int k = 3, n = 10;
KQueues ks= new KQueues(k, n);
// Let us put some items in queue number 2
ks.enqueue(15, 2);
ks.enqueue(45, 2);
// Let us put some items in queue number 1
ks.enqueue(17, 1);
ks.enqueue(49, 1);
ks.enqueue(39, 1);
// Let us put some items in queue number 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) );
}
// To check whether queue number 'i' is empty or not
private boolean isEmpty(int i) {
return front[i] == -1;
}
// To dequeue an from queue number 'i' where i is from 0 to k-1
private boolean isFull(int i) {
return free == -1;
}
// To enqueue an item in queue number 'j' where j is from 0 to 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 {
// Update next of rear and then rear for queue number 'j'
next[rear[j]] = free;
rear[j] = free;
}
next[free] = -1;
// Put the item in array
arr[free] = item;
// Update index of free slot to index of next slot in free list
free = nextFree;
}
// To dequeue an from queue number 'i' where i is from 0 to k-1
private int dequeue(int i) {
// Underflow checkSAS
if(isEmpty(i)) {
System.out.println("Stack underflow");
return Integer.MIN_VALUE;
}
// Find index of front item in queue number 'i'
int frontIndex = front[i];
// Change top to store next of previous top
front[i] = next[frontIndex];
// Attach the previous front to the beginning of free list
next[frontIndex] = free;
free = frontIndex;
return arr[frontIndex];
}
}
Python3
# A Python program to demonstrate implementation of k queues in a single
# array in time and space efficient way
class KQueues:
def __init__(self, number_of_queues, array_length):
self.number_of_queues = number_of_queues
self.array_length = array_length
self.array = [-1] * array_length
self.front = [-1] * number_of_queues
self.rear = [-1] * number_of_queues
self.next_array = list(range(1, array_length))
self.next_array.append(-1)
self.free = 0
# To check whether the current queue_number is empty or not
def is_empty(self, queue_number):
return True if self.front[queue_number] == -1 else False
# To check whether the current queue_number is full or not
def is_full(self, queue_number):
return True if self.free == -1 else False
# To enqueue the given item in the given queue_number where
# queue_number is from 0 to number_of_queues-1
def enqueue(self, item, queue_number):
if self.is_full(queue_number):
print("Queue FULL")
return
next_free = self.next_array[self.free]
if self.is_empty(queue_number):
self.front[queue_number] = self.rear[queue_number] = self.free
else:
self.next_array[self.rear[queue_number]] = self.free
self.rear[queue_number] = self.free
self.next_array[self.free] = -1
self.array[self.free] = item
self.free = next_free
# To dequeue an item from the given queue_number where
# queue_number is from 0 to number_of_queues-1
def dequeue(self, queue_number):
if self.is_empty(queue_number):
print("Queue EMPTY")
return
front_index = self.front[queue_number]
self.front[queue_number] = self.next_array[front_index]
self.next_array[front_index] = self.free
self.free = front_index
return self.array[front_index]
if __name__ == "__main__":
# Let us create 3 queue in an array of size 10
ks = KQueues(3, 10)
# Let us put some items in queue number 2
ks.enqueue(15, 2)
ks.enqueue(45, 2)
# Let us put some items in queue number 1
ks.enqueue(17, 1);
ks.enqueue(49, 1);
ks.enqueue(39, 1);
# Let us put some items in queue number 0
ks.enqueue(11, 0);
ks.enqueue(9, 0);
ks.enqueue(7, 0);
print("Dequeued element from queue 2 is {}".format(ks.dequeue(2)))
print("Dequeued element from queue 1 is {}".format(ks.dequeue(1)))
print("Dequeued element from queue 0 is {}".format(ks.dequeue(0)))
C#
// A C# program to demonstrate implementation of k queues in a single
// array in time and space efficient way
using System;
public class KQueues
{
int k;
int n;
int[] arr;
int[] front;
int[] rear;
int[] next;
int free;
KQueues(int k, int n)
{
// Initialize n and k, and
// allocate memory for all arrays
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];
// Initialize all queues as empty
for(int i = 0; i < k; i++)
{
front[i] = rear[i] = -1;
}
// Initialize all spaces as free
free = 0;
for(int i = 0; i < n - 1; i++)
{
next[i] = i + 1;
}
next[n - 1] = -1;
}
public static void Main(String[] args)
{
// Let us create 3 queue in an array of size 10
int k = 3, n = 10;
KQueues ks = new KQueues(k, n);
// Let us put some items in queue number 2
ks.enqueue(15, 2);
ks.enqueue(45, 2);
// Let us put some items in queue number 1
ks.enqueue(17, 1);
ks.enqueue(49, 1);
ks.enqueue(39, 1);
// Let us put some items in queue number 0
ks.enqueue(11, 0);
ks.enqueue(9, 0);
ks.enqueue(7, 0);
Console.WriteLine("Dequeued element from queue 2 is " +
ks.dequeue(2));
Console.WriteLine("Dequeued element from queue 1 is " +
ks.dequeue(1));
Console.WriteLine("Dequeued element from queue 0 is " +
ks.dequeue(0) );
}
// To check whether queue number 'i' is empty or not
private bool isEmpty(int i)
{
return front[i] == -1;
}
// To dequeue an from queue
// number 'i' where i is from 0 to k-1
private bool isFull(int i)
{
return free == -1;
}
// To enqueue an item in queue
// number 'j' where j is from 0 to k-1
private void enqueue(int item, int j)
{
if(isFull(j))
{
Console.WriteLine("queue overflow");
return;
}
int nextFree = next[free];
if(isEmpty(j))
{
rear[j] = front[j] = free;
}
else
{
// Update next of rear and then
// rear for queue number 'j'
next[rear[j]] = free;
rear[j] = free;
}
next[free] = -1;
// Put the item in array
arr[free] = item;
// Update index of free slot to
// index of next slot in free list
free = nextFree;
}
// To dequeue an from queue
// number 'i' where i is from 0 to k-1
private int dequeue(int i)
{
// Underflow checkSAS
if(isEmpty(i))
{
Console.WriteLine("Stack underflow");
return int.MinValue;
}
// Find index of front item in queue number 'i'
int frontIndex = front[i];
// Change top to store next of previous top
front[i] = next[frontIndex];
// Attach the previous front to the beginning of free list
next[frontIndex] = free;
free = frontIndex;
return arr[frontIndex];
}
}
// This code is contributed by aashish1995
Javascript
<script>
// A Javascript program to demonstrate implementation of k queues in a single
// array in time and space efficient way
class KQueues
{
constructor(k,n)
{
// Initialize n and k, and allocate memory for all arrays
this.k = k;
this.n = n;
this.arr = new Array(n);
this.front = new Array(k);
this.rear = new Array(k);
this.next = new Array(n);
// Initialize all queues as empty
for(let i= 0; i< k; i++) {
this.front[i] = this.rear[i] = -1;
}
// Initialize all spaces as free
this.free = 0;
for(let i= 0; i< n-1; i++) {
this.next[i] = i+1;
}
this.next[n-1] = -1;
}
// To check whether queue number 'i' is empty or not
isEmpty(i)
{
return this.front[i] == -1;
}
// To dequeue an from queue number 'i' where i is from 0 to k-1
isFull(i)
{
return this.free == -1;
}
// To enqueue an item in queue number 'j' where j is from 0 to k-1
enqueue(item,j)
{
if(this.isFull(j)) {
document.write("queue overflow<br>");
return;
}
let nextFree = this.next[this.free];
if(this.isEmpty(j)) {
this.rear[j] = this.front[j] = this.free;
}else {
// Update next of rear and then rear for queue number 'j'
this.next[this.rear[j]] = this.free;
this.rear[j] = this.free;
}
this.next[this.free] = -1;
// Put the item in array
this.arr[this.free] = item;
// Update index of free slot to index of next slot in free list
this.free = nextFree;
}
// To dequeue an from queue number 'i' where i is from 0 to k-1
dequeue(i)
{
// Underflow checkSAS
if(this.isEmpty(i)) {
document.write("Stack underflow<br>");
return Number.MIN_VALUE;
}
// Find index of front item in queue number 'i'
let frontIndex = this.front[i];
// Change top to store next of previous top
this.front[i] = this.next[frontIndex];
// Attach the previous front to the beginning of free list
this.next[frontIndex] = this.free;
this.free = frontIndex;
return this.arr[frontIndex];
}
}
// Let us create 3 queue in an array of size 10
let k = 3, n = 10;
let ks= new KQueues(k, n);
// Let us put some items in queue number 2
ks.enqueue(15, 2);
ks.enqueue(45, 2);
// Let us put some items in queue number 1
ks.enqueue(17, 1);
ks.enqueue(49, 1);
ks.enqueue(39, 1);
// Let us put some items in queue number 0
ks.enqueue(11, 0);
ks.enqueue(9, 0);
ks.enqueue(7, 0);
document.write("Dequeued element from queue 2 is " +
ks.dequeue(2)+"<br>");
document.write("Dequeued element from queue 1 is " +
ks.dequeue(1)+"<br>");
document.write("Dequeued element from queue 0 is " +
ks.dequeue(0)+"<br>" );
// This code is contributed by avanitrachhadiya2155
</script>
Producción
Dequeued element from queue 2 is 15 Dequeued element from queue 1 is 17 Dequeued element from queue 0 is 11
Las complejidades temporales de enqueue() y dequeue() son O(1).
La mejor parte de la implementación anterior es que, si hay un espacio disponible en la cola, entonces un elemento se puede poner en cola en cualquiera de las colas, es decir, sin desperdicio de espacio. Este método requiere algo de espacio adicional. El espacio puede no ser un problema porque los elementos de la cola suelen ser grandes, por ejemplo, colas de empleados, estudiantes, etc., donde cada elemento tiene cientos de bytes. Para colas tan grandes, el espacio adicional utilizado es comparativamente mucho menor, ya que usamos tres arrays de enteros como espacio adicional.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA