Dada una pila de M elementos y una cola de N elementos ordenados. La tarea es encontrar los elementos comunes de la pila y la cola.
Ejemplos:
Entrada: pila = [1, 3, 5, 7], cola = [1, 2, 5, 9]
Salida: 5, 1
Explicación: 1 y 5 están presentes tanto en la pila como en la cola.Entrada: pila = [1, 3], cola = [2, 4]
Salida: No encontrado
Explicación: No hay ningún elemento común.
Enfoque: El problema dado se puede resolver con la ayuda de la siguiente idea:
Como ambos están ordenados, el elemento superior de la pila será el máximo y el primer elemento de la cola será el mínimo. Así que invierta cualquiera de ellos y compare los elementos en la parte superior de la pila y al frente de la cola para encontrar los elementos comunes.
Siga la ilustración a continuación para una mejor comprensión.
Ilustración:
Digamos, stack = [1, 3, 5, 7] donde 7 está en la parte superior y
la cola = [1, 2, 5, 9] donde 1 está al frente.Digamos que estamos invirtiendo la cola. Haga lo siguiente para invertir la cola:
- 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 = [1, 3, 5, 7, 1] y Cola = [2, 5, 9]
=> Después de la segunda iteración, Pila = [1, 3, 5, 7, 1, 2] and Queue = [5, 9]
=> Después de la tercera iteración, Stack = [1, 3, 5, 7, 1, 2, 5] and Queue = [9]
=> Después de la cuarta iteración, Stack = [1, 3, 5, 7, 1, 2, 5, 9] 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 = [1, 3, 5, 7, 1, 2, 5] y Cola = [9]
=> Después de la segunda iteración, Pila = [1, 3, 5, 7, 1, 2] and Queue = [9, 5]
=> Después de la tercera iteración, Stack = [1, 3, 5, 7, 1] and Queue = [9, 5, 2]
=> Después de la cuarta iteración, Stack = [1, 3, 5, 7] y Cola = [9, 5, 2, 1]Ahora lo siguiente para encontrar los elementos comunes.
1er paso:
=> parte superior de la pila < frente a la cola.
=> Frente de cola emergente.
=> Entonces la pila es [1, 3, 5, 7] y la cola [5, 2, 1]2do paso:
=> apilar arriba > hacer cola al frente
=> Hacer estallar la parte superior de la pila
=> Entonces apilar [1, 3, 5] y poner en cola [5, 2, 1]3er paso:
=> parte superior de la pila = parte delantera de la cola
=> Pop parte superior de la pila y parte delantera de la cola
=> Así que apila [1, 3] y pone en cola [2, 1]
=> Elementos comunes [5]4to paso:
=> parte superior de la pila > parte delantera de la cola
=> parte superior de la pila
=> Así que apila [1] y pone en cola [2, 1]5to Paso:
=> parte superior de la pila < frente a la cola.
=> Frente de cola emergente.
=> Entonces la pila es [1] y la cola [1]6to paso:
=> parte superior de la pila = parte delantera de la cola
=> Pop parte superior de la pila y parte delantera de la cola
=> Así que apila [] y hace cola []
=> Elementos comunes [5, 1] .
Siga los pasos a continuación para resolver el problema:
- Invertir la cola .
- Atraviese la pila y la cola mientras que la pila y la cola no se vacían.
- Si parte superior de la pila = parte delantera de la cola, ese es un elemento común.
- De lo contrario, si, parte superior de la pila> frente a la cola, extrae el elemento superior de la pila.
- De lo contrario, parte superior de la pila < frente a la cola, extrae el elemento frontal de la pila.
- Imprime los elementos comunes.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find common element
// of stack and queue
vector<int> findCommonElement(stack<int>& St,
queue<int>& Q)
{
// Initialize size of queue Q to 0
int Size = 0;
vector<int> v;
// Put every element of queue into stack
// and calculate size of queue
while (!Q.empty()) {
St.push(Q.front());
Q.pop();
Size++;
}
// Put extra element of stack into queue
// again extra element of stack is the
// element coming from queue. Now, the
// queue is reverse
while (Size != 0) {
Q.push(St.top());
St.pop();
Size--;
}
// Traverse while stack and queue is not
// empty
while (!St.empty() && !Q.empty()) {
// Top element of stack
int a = St.top();
// Front element of queue
int b = Q.front();
// Push the common element
// in vector if a = b
if (a == b)
v.push_back(a);
// Else pop the larger value
// from its container
(a > b) ? St.pop() : Q.pop();
}
return v;
}
// Driver Code
int main()
{
stack<int> St;
queue<int> Q;
// Fill element into stack
St.push(1);
St.push(3);
St.push(5);
St.push(7);
// Fill element into queue
Q.push(1);
Q.push(2);
Q.push(5);
Q.push(9);
// Find common element if exists
vector<int> v = findCommonElement(St, Q);
if (v.size() == 0)
cout << "Not Found" << endl;
for (auto i : v)
cout << i << " ";
return 0;
}
Java
// Java code to implement the above approach
import java.util.ArrayList;
class GFG
{
// Function to find common element
// of stack and queue
static ArrayList<Integer>
findCommonElement(ArrayList<Integer> St,
ArrayList<Integer> Q)
{
// Initialize size of queue Q to 0
int Size = 0;
ArrayList<Integer> v = new ArrayList<Integer>();
// Put every element of queue into stack
// and calculate size of queue
while (Q.size() != 0) {
St.add(Q.get(0));
Q.remove(0);
Size++;
}
// Put extra element of stack into queue
// again extra element of stack is the
// element coming from queue. Now, the
// queue is reverse
while (Size != 0) {
Q.add(St.get(St.size() - 1));
St.remove(St.size() - 1);
Size--;
}
// Traverse while stack and queue is not
// empty
while (St.size() != 0 && Q.size() != 0) {
// Top element of stack
int a = St.get(St.size() - 1);
// Front element of queue
int b = Q.get(0);
// Push the common element
// in vector if a = b
if (a == b)
v.add(a);
// Else pop the larger value
// from its container
if (a > b)
St.remove(St.size() - 1);
else
Q.remove(0);
}
return v;
}
public static void main(String[] args)
{
// Driver Code
ArrayList<Integer> St = new ArrayList<Integer>();
ArrayList<Integer> Q = new ArrayList<Integer>();
// Fill element into stack
St.add(1);
St.add(3);
St.add(5);
St.add(7);
// Fill element into queue
Q.add(1);
Q.add(2);
Q.add(5);
Q.add(9);
// Find common element if exists
ArrayList<Integer> v = findCommonElement(St, Q);
if (v.size() == 0)
System.out.print("Not Found");
for (int i = 0; i < v.size(); i++)
System.out.print(v.get(i) + " ");
}
}
// this code is contributed by phasing17
Python3
# Python code to implement the above approach
# Function to find common element
# of stack and queue
def findCommonElement(St, Q):
# Initialize size of queue Q to 0
Size = 0
v = []
# Put every element of queue into stack
# and calculate size of queue
while len(Q) != 0:
St.append(Q[0])
Q = Q[1:]
Size += 1
# Put extra element of stack into queue
# again extra element of stack is the
# element coming from queue. Now, the
# queue is reverse
while (Size != 0):
Q.append(St[len(St) - 1])
St.pop()
Size -= 1
# Traverse while stack and queue is not
# empty
while (len(St) != 0 and len(Q) != 0):
# Top element of stack
a = St[len(St) - 1]
# Front element of queue
b = Q[0]
# append the common element
# in vector if a = b
if (a == b):
v.append(a)
# Else pop the larger value
# from its container
if (a > b):
St.pop()
else:
Q = Q[1:]
return v
# Driver Code
St = []
Q = []
# Fill element into stack
St.append(1)
St.append(3)
St.append(5)
St.append(7)
# Fill element into queue
Q.append(1)
Q.append(2)
Q.append(5)
Q.append(9)
# Find common element if exists
v = findCommonElement(St, Q)
if (len(v) == 0):
print("Not Found")
for i in v:
print(i,end=" ")
# This code is contributed by shinjanpatra
C#
// C# code to implement the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to find common element
// of stack and queue
public static List<int> findCommonElement(List<int> St,
List<int> Q)
{
// Initialize size of queue Q to 0
int Size = 0;
List<int> v = new List<int>();
// Put every element of queue into stack
// and calculate size of queue
while (Q.Count != 0) {
St.Add(Q[0]);
Q.RemoveAt(0);
Size++;
}
// Put extra element of stack into queue
// again extra element of stack is the
// element coming from queue. Now, the
// queue is reverse
while (Size != 0) {
Q.Add(St[St.Count - 1]);
St.RemoveAt(St.Count - 1);
Size--;
}
// Traverse while stack and queue is not
// empty
while (St.Count != 0 && Q.Count != 0) {
// Top element of stack
int a = St[St.Count - 1];
// Front element of queue
int b = Q[0];
// Push the common element
// in vector if a = b
if (a == b)
v.Add(a);
// Else pop the larger value
// from its container
if (a > b)
St.RemoveAt(St.Count - 1);
else
Q.RemoveAt(0);
}
return v;
}
public static void Main(string[] args)
{
// Driver Code
List<int> St = new List<int>();
List<int> Q = new List<int>();
// Fill element into stack
St.Add(1);
St.Add(3);
St.Add(5);
St.Add(7);
// Fill element into queue
Q.Add(1);
Q.Add(2);
Q.Add(5);
Q.Add(9);
// Find common element if exists
List<int> v = findCommonElement(St, Q);
if (v.Count == 0)
Console.WriteLine("Not Found");
foreach(var ele in v) Console.Write(ele + " ");
}
}
//This code is contributed by phasing17
Javascript
<script>
// JavaScript code to implement the above approach
// Function to find common element
// of stack and queue
const findCommonElement = (St, Q) => {
// Initialize size of queue Q to 0
let Size = 0;
let v = [];
// Put every element of queue into stack
// and calculate size of queue
while (Q.length != 0) {
St.push(Q[0]);
Q.shift();
Size++;
}
// Put extra element of stack into queue
// again extra element of stack is the
// element coming from queue. Now, the
// queue is reverse
while (Size != 0) {
Q.push(St[St.length - 1]);
St.pop();
Size--;
}
// Traverse while stack and queue is not
// empty
while (St.length != 0 && Q.length != 0)
{
// Top element of stack
let a = St[St.length - 1];
// Front element of queue
let b = Q[0];
// Push the common element
// in vector if a = b
if (a == b)
v.push(a);
// Else pop the larger value
// from its container
(a > b) ? St.pop() : Q.shift();
}
return v;
}
// Driver Code
let St = [];
let Q = [];
// Fill element into stack
St.push(1);
St.push(3);
St.push(5);
St.push(7);
// Fill element into queue
Q.push(1);
Q.push(2);
Q.push(5);
Q.push(9);
// Find common element if exists
let v = findCommonElement(St, Q);
if (v.length == 0)
document.write("Not Found");
for (let i in v)
document.write(`${v[i]} `);
// This code is contributed by rakeshsahni
</script>
5 1
Complejidad de tiempo: O(M+N) donde M = tamaño de la cola y N = tamaño de la pila
Espacio auxiliar: O(M) para invertir elementos de la cola
Publicación traducida automáticamente
Artículo escrito por akashjha2671 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA