Dada una cola y la tarea es ordenarla usando recursividad sin usar ningún bucle. Solo podemos usar las siguientes funciones de cola:
vacío (q): comprueba si la cola está vacía o no.
push(q): Agrega un nuevo elemento a la cola.
pop(q): elimina el elemento frontal de la cola.
size(q): Devuelve el número de elementos en una cola.
front(q): Devuelve el valor del elemento front sin eliminarlo.
Ejemplos:
Entrada: cola = {10, 7, 16, 9, 20, 5}
Salida: 5 7 9 10 16 20
Entrada: cola = {0, -2, -1, 2, 3, 1}
Salida: -2 -1 0 1 2 3
Enfoque: la idea de la solución es mantener todos los valores en la pila de llamadas de función hasta que la cola se vacíe. Cuando la cola se vacía, inserte todos los elementos retenidos uno por uno en orden ordenado. Aquí el orden ordenado es importante.
¿Cómo gestionar el orden clasificado?
Siempre que obtenga el elemento de la pila de llamadas de función, primero calcule el tamaño de la cola y compárelo con los elementos de la cola. Aquí se presentan dos casos:
- Si el elemento (devuelto por la pila de llamadas de función) es mayor que el elemento frontal de la cola, elimine el elemento frontal y coloque este elemento en la misma cola disminuyendo el tamaño.
- Si el elemento es menor que el elemento frontal de la cola, ponga en cola el elemento en la cola y elimine el elemento restante de la cola y ponga en cola disminuyendo el tamaño, repita los casos 1 y 2 a menos que el tamaño sea cero. Tenga cuidado con una cosa, si el tamaño se convirtió en cero y su elemento sigue siendo mayor que todos los elementos de la cola, entonces empuje su elemento a la cola.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to push element in last by
// popping from front until size becomes 0
void FrontToLast(queue<int>& q, int qsize)
{
// Base condition
if (qsize <= 0)
return;
// pop front element and push
// this last in a queue
q.push(q.front());
q.pop();
// Recursive call for pushing element
FrontToLast(q, qsize - 1);
}
// Function to push an element in the queue
// while maintaining the sorted order
void pushInQueue(queue<int>& q, int temp, int qsize)
{
// Base condition
if (q.empty() || qsize == 0) {
q.push(temp);
return;
}
// If current element is less than
// the element at the front
else if (temp <= q.front()) {
// Call stack with front of queue
q.push(temp);
// Recursive call for inserting a front
// element of the queue to the last
FrontToLast(q, qsize);
}
else {
// Push front element into
// last in a queue
q.push(q.front());
q.pop();
// Recursive call for pushing
// element in a queue
pushInQueue(q, temp, qsize - 1);
}
}
// Function to sort the given
// queue using recursion
void sortQueue(queue<int>& q)
{
// Return if queue is empty
if (q.empty())
return;
// Get the front element which will
// be stored in this variable
// throughout the recursion stack
int temp = q.front();
// Remove the front element
q.pop();
// Recursive call
sortQueue(q);
// Push the current element into the queue
// according to the sorting order
pushInQueue(q, temp, q.size());
}
// Driver code
int main()
{
// Push elements to the queue
queue<int> qu;
qu.push(10);
qu.push(7);
qu.push(16);
qu.push(9);
qu.push(20);
qu.push(5);
// Sort the queue
sortQueue(qu);
// Print the elements of the
// queue after sorting
while (!qu.empty()) {
cout << qu.front() << " ";
qu.pop();
}
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to push element in last by
// popping from front until size becomes 0
static void FrontToLast(Queue<Integer> q,
int qsize)
{
// Base condition
if (qsize <= 0)
return;
// pop front element and push
// this last in a queue
q.add(q.peek());
q.remove();
// Recursive call for pushing element
FrontToLast(q, qsize - 1);
}
// Function to push an element in the queue
// while maintaining the sorted order
static void pushInQueue(Queue<Integer> q,
int temp, int qsize)
{
// Base condition
if (q.isEmpty() || qsize == 0)
{
q.add(temp);
return;
}
// If current element is less than
// the element at the front
else if (temp <= q.peek())
{
// Call stack with front of queue
q.add(temp);
// Recursive call for inserting a front
// element of the queue to the last
FrontToLast(q, qsize);
}
else
{
// Push front element into
// last in a queue
q.add(q.peek());
q.remove();
// Recursive call for pushing
// element in a queue
pushInQueue(q, temp, qsize - 1);
}
}
// Function to sort the given
// queue using recursion
static void sortQueue(Queue<Integer> q)
{
// Return if queue is empty
if (q.isEmpty())
return;
// Get the front element which will
// be stored in this variable
// throughout the recursion stack
int temp = q.peek();
// Remove the front element
q.remove();
// Recursive call
sortQueue(q);
// Push the current element into the queue
// according to the sorting order
pushInQueue(q, temp, q.size());
}
// Driver code
public static void main(String[] args)
{
// Push elements to the queue
Queue<Integer> qu = new LinkedList<>();
qu.add(10);
qu.add(7);
qu.add(16);
qu.add(9);
qu.add(20);
qu.add(5);
// Sort the queue
sortQueue(qu);
// Print the elements of the
// queue after sorting
while (!qu.isEmpty())
{
System.out.print(qu.peek() + " ");
qu.remove();
}
}
}
// This code is contributed by PrinciRaj1992
Python3
# defining a class Queue class Queue: def __init__(self): self.queue = [] def put(self, item): self.queue.append(item) def get(self): if len(self.queue) < 1: return None return self.queue.pop(0) def front(self): return self.queue[0] def size(self): return len(self.queue) def empty(self): return not(len(self.queue)) # Function to push element in last by # popping from front until size becomes 0 def FrontToLast(q, qsize) : # Base condition if qsize <= 0: return # pop front element and push # this last in a queue q.put(q.get()) # Recursive call for pushing element FrontToLast(q, qsize - 1) # Function to push an element in the queue # while maintaining the sorted order def pushInQueue(q, temp, qsize) : # Base condition if q.empty() or qsize == 0: q.put(temp) return # If current element is less than # the element at the front elif temp <= q.front() : # Call stack with front of queue q.put(temp) # Recursive call for inserting a front # element of the queue to the last FrontToLast(q, qsize) else : # Push front element into # last in a queue q.put(q.get()) # Recursive call for pushing # element in a queue pushInQueue(q, temp, qsize - 1) # Function to sort the given # queue using recursion def sortQueue(q): # Return if queue is empty if q.empty(): return # Get the front element which will # be stored in this variable # throughout the recursion stack temp = q.get() # Recursive call sortQueue(q) # Push the current element into the queue # according to the sorting order pushInQueue(q, temp, q.size()) # Driver code qu = Queue() # Data is inserted into Queue # using put() Data is inserted # at the end qu.put(10) qu.put(7) qu.put(16) qu.put(9) qu.put(20) qu.put(5) # Sort the queue sortQueue(qu) # Print the elements of the # queue after sorting while not qu.empty(): print(qu.get(), end = ' ') # This code is contributed by Sadik Ali
C#
// Program to print the given pattern
using System;
using System.Collections.Generic;
class GFG
{
// Function to push element in last by
// popping from front until size becomes 0
static void FrontToLast(Queue<int> q,
int qsize)
{
// Base condition
if (qsize <= 0)
return;
// pop front element and push
// this last in a queue
q.Enqueue(q.Peek());
q.Dequeue();
// Recursive call for pushing element
FrontToLast(q, qsize - 1);
}
// Function to push an element in the queue
// while maintaining the sorted order
static void pushInQueue(Queue<int> q,
int temp, int qsize)
{
// Base condition
if (q.Count == 0 || qsize == 0)
{
q.Enqueue(temp);
return;
}
// If current element is less than
// the element at the front
else if (temp <= q.Peek())
{
// Call stack with front of queue
q.Enqueue(temp);
// Recursive call for inserting a front
// element of the queue to the last
FrontToLast(q, qsize);
}
else
{
// Push front element into
// last in a queue
q.Enqueue(q.Peek());
q.Dequeue();
// Recursive call for pushing
// element in a queue
pushInQueue(q, temp, qsize - 1);
}
}
// Function to sort the given
// queue using recursion
static void sortQueue(Queue<int> q)
{
// Return if queue is empty
if (q.Count==0)
return;
// Get the front element which will
// be stored in this variable
// throughout the recursion stack
int temp = q.Peek();
// Remove the front element
q.Dequeue();
// Recursive call
sortQueue(q);
// Push the current element into the queue
// according to the sorting order
pushInQueue(q, temp, q.Count);
}
// Driver code
public static void Main(String[] args)
{
// Push elements to the queue
Queue<int> qu = new Queue<int>();
qu.Enqueue(10);
qu.Enqueue(7);
qu.Enqueue(16);
qu.Enqueue(9);
qu.Enqueue(20);
qu.Enqueue(5);
// Sort the queue
sortQueue(qu);
// Print the elements of the
// queue after sorting
while (qu.Count != 0)
{
Console.Write(qu.Peek() + " ");
qu.Dequeue();
}
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript implementation of the approach
// Function to push element in last by
// popping from front until size becomes 0
function FrontToLast(q, qsize)
{
// Base condition
if (qsize <= 0)
return;
// pop front element and push
// this last in a queue
q.push(q[0]);
q.shift();
// Recursive call for pushing element
FrontToLast(q, qsize - 1);
}
// Function to push an element in the queue
// while maintaining the sorted order
function pushInQueue(q, temp, qsize)
{
// Base condition
if (q.length == 0 || qsize == 0)
{
q.push(temp);
return;
}
// If current element is less than
// the element at the front
else if (temp <= q[0])
{
// Call stack with front of queue
q.push(temp);
// Recursive call for inserting a front
// element of the queue to the last
FrontToLast(q, qsize);
}
else
{
// Push front element into
// last in a queue
q.push(q[0]);
q.shift();
// Recursive call for pushing
// element in a queue
pushInQueue(q, temp, qsize - 1);
}
}
// Function to sort the given
// queue using recursion
function sortQueue(q)
{
// Return if queue is empty
if (q.length==0)
return;
// Get the front element which will
// be stored in this variable
// throughout the recursion stack
let temp = q[0];
// Remove the front element
q.shift();
// Recursive call
sortQueue(q);
// Push the current element into the queue
// according to the sorting order
pushInQueue(q, temp, q.length);
}
// Push elements to the queue
let qu = [];
qu.push(10);
qu.push(7);
qu.push(16);
qu.push(9);
qu.push(20);
qu.push(5);
// Sort the queue
sortQueue(qu);
// Print the elements of the
// queue after sorting
while (qu.length != 0)
{
document.write(qu[0] + " ");
qu.shift();
}
// This code is contributed by mukesh07.
</script>
Producción:
5 7 9 10 16 20
Publicación traducida automáticamente
Artículo escrito por MohammadMudassir y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA