Intercambie elementos de Stack y Queue sin cambiar el orden

Dada una pila St de M elementos y una cola Q de N elementos. La tarea es poner cada elemento de la pila en la cola y cada elemento de la cola en la pila sin cambiar su orden.

Ejemplos :

Entrada : St= {4, 3, 2, 1}, Q = {8, 7, 6, 5}
Salida : St = {8, 7, 6, 5}, Q = {1, 2, 3, 4}

Entrada: St = {0, 1}, Q = {2, 3}
Salida: St = {2, 3}, Q = {0, 1}

Enfoque ingenuo: el enfoque básico es almacenar los elementos de la pila y la cola en una array separada y luego volver a colocarlos en la cola y la pila.

Complejidad temporal: O(N + M)
Espacio auxiliar: O(N + M)

Enfoque optimizado : este problema se puede resolver sin utilizar espacio adicional mediante el uso de las propiedades de pila y cola de último en entrar, primero en salir y primero en entrar, primero en salir .

Siga los pasos para resolver el problema:

1. Coloque todos los elementos de la cola en la pila.
2. Vuelva a colocar elementos adicionales de la pila en la cola, el elemento adicional de la pila es el elemento que proviene de la cola. Ahora, la cola se invierte.
3. Ahora, ponga todos los elementos de la pila en la cola.
4. Por último, coloque los elementos originales de la cola en la pila.
5. Ahora repita el primer y segundo paso nuevamente para mantener el orden de los elementos de la pila en la cola.

Siga las ilustraciones a continuación para comprender mejor el enfoque:

Ilustraciones:

Considere la pila = [1, 2, 3, 4] donde 1 está en la parte superior y la cola = [8, 7, 6, 5] donde 8 está al frente.

En el primer paso :
uno por uno extraiga el elemento de la cola (es decir, todos los elementos de la cola) y empújelos a la pila.
Después de la primera iteración, Pila = [8, 1, 2, 3, 4] y cola = [7, 6, 5] Después de la segunda iteración, Pila = [7, 8, 1, 2,
3, 4] y cola = [ 6, 5]
Después de la tercera iteración, Pila = [6, 7, 8, 1, 2, 3, 4] y cola = [5]
Después de la cuarta iteración, Pila = [5, 6, 7, 8, 1, 2, 3, 4] y cola = []

En el segundo paso :
uno por uno extraiga el elemento de la pila (es decir, que viene de la cola) y empújelo a la cola.
Después de la primera iteración, Pila = [6, 7, 8, 1, 2, 3, 4] y cola = [5]
Después de la segunda iteración, Pila = [7, 8, 1, 2, 3, 4] y cola = [ 5, 6]
Después de la tercera iteración, Pila = [8, 1, 2, 3, 4] y cola = [5, 6, 7] Después de la cuarta
iteración, Pila = [1, 2, 3, 4] y cola = [ 5, 6, 7, 8]

En el tercer paso :
uno por uno, extraiga el elemento de la pila (es decir, queden todos los elementos) y colóquelo en la cola.
Después de la primera iteración, Pila = [2, 3, 4] y cola = [5, 6, 7, 8, 1] Después de la segunda iteración, Pila = [3
, 4] y cola = [5, 6, 7, 8, 1, 2]
Después de la tercera iteración, Pila = [4] y cola = [5, 6, 7, 8, 1, 2, 3] Después de la cuarta
iteración, Pila = [] y cola = [5, 6, 7, 8 , 1, 2, 3, 4]

En el cuarto paso :
uno por uno extraiga el elemento de la cola (es decir, el único elemento de la cola antes del primer paso) y empújelo a la pila.
Después de la primera iteración, Pila = [5] y cola = [6, 7, 8, 1, 2, 3, 4] Después de la segunda iteración, Pila = [
6, 5] y cola = [7, 8, 1, 2, 3, 4]
Después de la tercera iteración, Pila = [7, 6, 5] y cola = [8, 1, 2, 3, 4] Después de la cuarta iteración, Pila = [
8, 7, 6, 5] y cola = [ 1, 2, 3, 4]

Ahora repita el primer y segundo paso.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to Put every element of stack
// into queue and queue into stack
// without changing its order
void changeElement(stack<int>& St,
                   queue<int>& Q)
{
 
    // Calculate size of queue Q
    int Size = Q.size();
    int Temp = Size;
    int N = St.size();
 
    // Put every element of queue into stack
    while (!Q.empty()) {
        St.push(Q.front());
        Q.pop();
    }
 
    // Put extra element of stack into
    // queue again, extra element of stack
    // is the element coming from queue.
    // Now, the queue is reversed
    while (Size != 0) {
        Q.push(St.top());
        St.pop();
        Size--;
    }
 
    // Put every element of stack into queue
    while (!St.empty()) {
        Q.push(St.top());
        St.pop();
    }
 
    Size = Temp;
 
    // Put initial element of queue
    // into stack
    while (Size != 0) {
        St.push(Q.front());
        Q.pop();
        Size--;
    }
 
    // Repeat the first and second steps
    while (!Q.empty()) {
        St.push(Q.front());
        Q.pop();
    }
    while (N != 0) {
        Q.push(St.top());
        St.pop();
        N--;
    }
}
 
// Function to traverse till stack is
// not empty and print the element in it
void printStack(stack<int>& St)
{
 
    while (!St.empty()) {
        cout << St.top() << " ";
        St.pop();
    }
    cout << endl;
}
 
// Function to traverse till queue is not
// empty and print the element in it
void printQueue(queue<int>& Q)
{
 
    while (!Q.empty()) {
        cout << Q.front() << " ";
        Q.pop();
    }
    cout << endl;
}
 
// Driver Code
int main()
{
    stack<int> St;
    queue<int> Q;
 
    // Fill element into stack
    St.push(4);
    St.push(3);
    St.push(2);
    St.push(1);
 
    // Fill element into queue
    Q.push(8);
    Q.push(7);
    Q.push(6);
    Q.push(5);
 
    changeElement(St, Q);
    cout << "Stack = ";
    printStack(St);
    cout << "Queue = ";
    printQueue(Q);
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.*;
 
public class GFG {
 
    // Function to Put every element of stack
    // into queue and queue into stack
    // without changing its order
    static void changeElement(Stack<Integer> St,
                              Deque<Integer> Q)
    {
 
        // Calculate size of queue Q
        int Size = Q.size();
        int Temp = Size;
        int N = St.size();
 
        // Put every element of queue into stack
        while (Q.size() > 0) {
            St.push(Q.element());
            Q.remove();
        }
 
        // Put extra element of stack into
        // queue again, extra element of stack
        // is the element coming from queue.
        // Now, the queue is reversed
        while (Size > 0) {
            Q.add(St.peek());
            St.pop();
            Size--;
        }
 
        // Put every element of stack into queue
        while (St.size() > 0) {
            Q.add(St.peek());
            St.pop();
        }
 
        Size = Temp;
 
        // Put initial element of queue
        // into stack
        while (Size > 0) {
            St.push(Q.element());
            Q.remove();
            Size--;
        }
 
        // Repeat the first and second steps
        while (Q.size() > 0) {
            St.push(Q.element());
            Q.remove();
        }
        while (N > 0) {
            Q.add(St.peek());
            St.pop();
            N--;
        }
    }
 
    // Function to traverse till stack is
    // not empty and print the element in it
    static void printStack(Stack<Integer> St)
    {
 
        while (St.size() > 0) {
            System.out.print(St.peek() + " ");
            St.pop();
        }
        System.out.println();
    }
 
    // Function to traverse till queue is not
    // empty and print the element in it
    static void printQueue(Deque<Integer> Q)
    {
 
        while (Q.size() > 0) {
            System.out.print(Q.removeLast() + " ");
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        Stack<Integer> St = new Stack<>();
        Deque<Integer> Q = new LinkedList<>();
        // Fill element into stack
        St.push(4);
        St.push(3);
        St.push(2);
        St.push(1);
 
        // Fill element into queue
        Q.add(8);
        Q.add(7);
        Q.add(6);
        Q.add(5);
 
        changeElement(St, Q);
        System.out.print("Stack = ");
        printStack(St);
        System.out.print("Queue = ");
        printQueue(Q);
    }
}
 
// This code is contributed by phasing17

# python3 program for the above approach
import collections
 
# Function to Put every element of stack
# into queue and queue into stack
# without changing its order
def changeElement(St, Q):
 
    # Calculate size of queue Q
    Size = len(Q)
    Temp = Size
    N = len(St)
 
    # Put every element of queue into stack
    while (len(Q) != 0):
        St.append(Q.popleft())
 
    # Put extra element of stack into
    # queue again, extra element of stack
    # is the element coming from queue.
    # Now, the queue is reversed
    while (Size != 0):
        Q.append(St.pop())
        Size -= 1
 
    # Put every element of stack into queue
    while (len(St) != 0):
        Q.append(St.pop())
 
    Size = Temp
 
    # Put initial element of queue
    # into stack
    while (Size != 0):
        St.append(Q.popleft())
 
        Size -= 1
 
    # Repeat the first and second steps
    while (len(Q) != 0):
        St.append(Q.popleft())
 
    while (N != 0):
        Q.append(St.pop())
 
        N -= 1
 
# Function to traverse till stack is
# not empty and print the element in it
def printStack(St):
 
    while (len(St) != 0):
        print(St.pop(), end=" ")
 
    print()
 
# Function to traverse till queue is not
# empty and print the element in it
def printQueue(Q):
 
    while (len(Q) != 0):
        print(Q.popleft(), end=" ")
 
    print()
 
# Driver Code
if __name__ == "__main__":
 
    St = collections.deque()
    Q = collections.deque()
 
    # Fill element into stack
    St.append(4)
    St.append(3)
    St.append(2)
    St.append(1)
 
    # Fill element into queue
    Q.append(8)
    Q.append(7)
    Q.append(6)
    Q.append(5)
 
    changeElement(St, Q)
    print("Stack = ", end="")
    printStack(St)
    print("Queue = ", end="")
    printQueue(Q)
 
    # This code is contributed by rakeshsahni

// C# program for the above approach
using System;
using System.Collections;
 
public class GFG{
 
  // Function to Put every element of stack
  // into queue and queue into stack
  // without changing its order
  static void changeElement(Stack St,
                            Queue  Q)
  {
 
    // Calculate size of queue Q
    int Size = Q.Count;
    int Temp = Size;
    int N = St.Count;
 
    // Put every element of queue into stack
    while (Q.Count > 0) {
      St.Push(Q.Peek());
      Q.Dequeue();
    }
 
    // Put extra element of stack into
    // queue again, extra element of stack
    // is the element coming from queue.
    // Now, the queue is reversed
    while (Size != 0) {
      Q.Enqueue(St.Peek());
      St.Pop();
      Size--;
    }
 
    // Put every element of stack into queue
    while (St.Count > 0) {
      Q.Enqueue(St.Peek());
      St.Pop();
    }
 
    Size = Temp;
 
    // Put initial element of queue
    // into stack
    while (Size != 0) {
      St.Push(Q.Peek());
      Q.Dequeue();
      Size--;
    }
 
    // Repeat the first and second steps
    while (Q.Count > 0) {
      St.Push(Q.Peek());
      Q.Dequeue();
    }
    while (N != 0) {
      Q.Enqueue(St.Peek());
      St.Pop();
      N--;
    }
  }
 
  // Function to traverse till stack is
  // not empty and print the element in it
  static void printStack(Stack St)
  {
 
    while (St.Count > 0) {
      Console.Write(St.Peek() + " ");
      St.Pop();
    }
    Console.WriteLine();
  }
 
  // Function to traverse till queue is not
  // empty and print the element in it
  static void printQueue(Queue Q)
  {
 
    while (Q.Count > 0) {
      Console.Write(Q.Peek() + " ");
      Q.Dequeue();
    }
  }
 
  // Driver Code
  static public void Main (){
 
    Stack St = new Stack();
    Queue Q = new Queue();
 
    // Fill element into stack
    St.Push(4);
    St.Push(3);
    St.Push(2);
    St.Push(1);
 
    // Fill element into queue
    Q.Enqueue(8);
    Q.Enqueue(7);
    Q.Enqueue(6);
    Q.Enqueue(5);
 
    changeElement(St, Q);
    Console.Write( "Stack = ");
    printStack(St);
    Console.Write("Queue = ");
    printQueue(Q);
  }
}
 
// This code is contributed by hrithikgarg03188.

<script>
 
// JavaScript program for the above approach
 
// Function to Put every element of stack
// into queue and queue into stack
// without changing its order
function changeElement(St, Q)
{
 
    // Calculate size of queue Q
    let Size = Q.length;
    let Temp = Size;
    let N = St.length;
 
    // Put every element of queue into stack
    while (Q.length !== 0) {
        St.push(Q.shift());
    }
 
    // Put extra element of stack into
    // queue again, extra element of stack
    // is the element coming from queue.
    // Now, the queue is reversed
    while (Size != 0) {
        Q.push(St.pop());
        Size--;
    }
 
    // Put every element of stack into queue
    while (St.length !== 0) {
        Q.push(St.pop());
    }
 
    Size = Temp;
 
    // Put initial element of queue
    // into stack
    while (Size != 0) {
        St.push(Q.shift());
        Size--;
    }
 
    // Repeat the first and second steps
    while (Q.length !== 0) {
        St.push(Q.shift());
    }
    while (N != 0) {
        Q.push(St.pop());
        N--;
    }
}
 
// Function to traverse till stack is
// not empty and print the element in it
function printStack(St)
{
 
    while (St.length !== 0) {
        document.write(St.pop()," ");
    }
    document.write("</br>");
}
 
// Function to traverse till queue is not
// empty and print the element in it
function printQueue(Q)
{
 
    while (Q.length !== 0) {
        document.write(Q.shift()," ");
    }
    document.write("</br>");
}
 
// Driver Code
 
let St = [];
let Q = [];
 
// Fill element into stack
St.push(4);
St.push(3);
St.push(2);
St.push(1);
 
// Fill element into queue
Q.push(8);
Q.push(7);
Q.push(6);
Q.push(5);
 
changeElement(St, Q);
document.write("Stack = ");
printStack(St);
document.write("Queue = ");
printQueue(Q);
 
// This code is contributed by shinjanpatra
 
</script>

Stack = 8 7 6 5 
Queue = 1 2 3 4 

Complejidad de Tiempo : O(M+N)
Espacio Auxiliar : O(1)