Dada una cola que consta de los primeros n números naturales (en orden aleatorio). La tarea es verificar si los elementos de la Cola dados se pueden organizar en orden creciente en otra Cola usando una pila. Las operaciones permitidas son:
1. Empujar y sacar elementos de la pila
2. Sacar (o sacar) de la cola dada.
3. Presione (O Enqueue) en la otra cola.
Ejemplos:
C++
// CPP Program to check if a queue of first
// n natural number can be sorted using a stack
#include <bits/stdc++.h>
using namespace std;
// Function to check if given queue element
// can be sorted into another queue using a
// stack.
bool checkSorted(int n, queue<int>& q)
{
stack<int> st;
int expected = 1;
int fnt;
// while given Queue is not empty.
while (!q.empty()) {
fnt = q.front();
q.pop();
// if front element is the expected element
if (fnt == expected)
expected++;
else {
// if stack is empty, push the element
if (st.empty()) {
st.push(fnt);
}
// if top element is less than element which
// need to be pushed, then return false.
else if (!st.empty() && st.top() < fnt) {
return false;
}
// else push into the stack.
else
st.push(fnt);
}
// while expected element are coming from
// stack, pop them out.
while (!st.empty() && st.top() == expected) {
st.pop();
expected++;
}
}
// if the final expected element value is equal
// to initial Queue size and the stack is empty.
if (expected - 1 == n && st.empty())
return true;
return false;
}
// Driven Program
int main()
{
queue<int> q;
q.push(5);
q.push(1);
q.push(2);
q.push(3);
q.push(4);
int n = q.size();
(checkSorted(n, q) ? (cout << "Yes") :
(cout << "No"));
return 0;
}
Java
// Java Program to check if a queue
// of first n natural number can
// be sorted using a stack
import java.io.*;
import java.util.*;
class GFG
{
static Queue<Integer> q =
new LinkedList<Integer>();
// Function to check if given
// queue element can be sorted
// into another queue using a stack.
static boolean checkSorted(int n)
{
Stack<Integer> st =
new Stack<Integer>();
int expected = 1;
int fnt;
// while given Queue
// is not empty.
while (q.size() != 0)
{
fnt = q.peek();
q.poll();
// if front element is
// the expected element
if (fnt == expected)
expected++;
else
{
// if stack is empty,
// push the element
if (st.size() == 0)
{
st.push(fnt);
}
// if top element is less than
// element which need to be
// pushed, then return false.
else if (st.size() != 0 &&
st.peek() < fnt)
{
return false;
}
// else push into the stack.
else
st.push(fnt);
}
// while expected element are
// coming from stack, pop them out.
while (st.size() != 0 &&
st.peek() == expected)
{
st.pop();
expected++;
}
}
// if the final expected element
// value is equal to initial Queue
// size and the stack is empty.
if (expected - 1 == n &&
st.size() == 0)
return true;
return false;
}
// Driver Code
public static void main(String args[])
{
q.add(5);
q.add(1);
q.add(2);
q.add(3);
q.add(4);
int n = q.size();
if (checkSorted(n))
System.out.print("Yes");
else
System.out.print("No");
}
}
// This code is contributed by
// Manish Shaw(manishshaw1)
Python3
# Python Program to check if a queue of first
# n natural number can be sorted using a stack
from queue import Queue
# Function to check if given queue element
# can be sorted into another queue using a
# stack.
def checkSorted(n, q):
st = []
expected = 1
fnt = None
# while given Queue is not empty.
while (not q.empty()):
fnt = q.queue[0]
q.get()
# if front element is the
# expected element
if (fnt == expected):
expected += 1
else:
# if stack is empty, put the element
if (len(st) == 0):
st.append(fnt)
# if top element is less than element which
# need to be puted, then return false.
elif (len(st) != 0 and st[-1] < fnt):
return False
# else put into the stack.
else:
st.append(fnt)
# while expected element are coming
# from stack, pop them out.
while (len(st) != 0 and
st[-1] == expected):
st.pop()
expected += 1
# if the final expected element value is equal
# to initial Queue size and the stack is empty.
if (expected - 1 == n and len(st) == 0):
return True
return False
# Driver Code
if __name__ == '__main__':
q = Queue()
q.put(5)
q.put(1)
q.put(2)
q.put(3)
q.put(4)
n = q.qsize()
if checkSorted(n, q):
print("Yes")
else:
print("No")
# This code is contributed by PranchalK
C#
// C# Program to check if a queue
// of first n natural number can
// be sorted using a stack
using System;
using System.Linq;
using System.Collections.Generic;
class GFG
{
// Function to check if given
// queue element can be sorted
// into another queue using a stack.
static bool checkSorted(int n,
ref Queue<int> q)
{
Stack<int> st = new Stack<int>();
int expected = 1;
int fnt;
// while given Queue
// is not empty.
while (q.Count != 0)
{
fnt = q.Peek();
q.Dequeue();
// if front element is
// the expected element
if (fnt == expected)
expected++;
else
{
// if stack is empty,
// push the element
if (st.Count == 0)
{
st.Push(fnt);
}
// if top element is less than
// element which need to be
// pushed, then return false.
else if (st.Count != 0 &&
st.Peek() < fnt)
{
return false;
}
// else push into the stack.
else
st.Push(fnt);
}
// while expected element are
// coming from stack, pop them out.
while (st.Count != 0 &&
st.Peek() == expected)
{
st.Pop();
expected++;
}
}
// if the final expected element
// value is equal to initial Queue
// size and the stack is empty.
if (expected - 1 == n &&
st.Count == 0)
return true;
return false;
}
// Driver Code
static void Main()
{
Queue<int> q = new Queue<int>();
q.Enqueue(5);
q.Enqueue(1);
q.Enqueue(2);
q.Enqueue(3);
q.Enqueue(4);
int n = q.Count;
if (checkSorted(n, ref q))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by
// Manish Shaw(manishshaw1)
Javascript
<script>
// Javascript Program to check if a queue
// of first n natural number can
// be sorted using a stack
let q = [];
// Function to check if given
// queue element can be sorted
// into another queue using a stack.
function checkSorted(n)
{
let st = [];
let expected = 1;
let fnt;
// while given Queue
// is not empty.
while (q.length != 0)
{
fnt = q[0];
q.shift();
// if front element is
// the expected element
if (fnt == expected)
expected++;
else
{
// if stack is empty,
// push the element
if (st.length == 0)
{
st.push(fnt);
}
// if top element is less than
// element which need to be
// pushed, then return false.
else if (st.length != 0 &&
st[st.length - 1] < fnt)
{
return false;
}
// else push into the stack.
else
st.push(fnt);
}
// while expected element are
// coming from stack, pop them out.
while (st.length != 0 &&
st[st.length - 1] == expected)
{
st.pop();
expected++;
}
}
// if the final expected element
// value is equal to initial Queue
// size and the stack is empty.
if ((expected - 1) == n && st.length == 0)
return true;
return false;
}
q.push(5);
q.push(1);
q.push(2);
q.push(3);
q.push(4);
let n = q.length;
if (checkSorted(n))
document.write("Yes");
else
document.write("No");
// This code is contributed by suresh07.
</script>