Dada una cola de enteros. La tarea es verificar si los elementos consecutivos en la cola son consecutivos por pares.
Ejemplos:
Input: 1 2 5 6 9 10 Output: Yes Input: 2 3 9 11 8 7 Output: No
Acercarse :
- Tome una variable n para almacenar el tamaño de la cola.
- Empuje un elemento a la cola que actúa como marcador.
- Ahora, si el tamaño de la cola es impar, comience a hacer estallar un par mientras n > 2. Además, mientras hace estallar estos pares, verifique su diferencia y disminuya n en 2, si la diferencia no es igual a 1, establezca el indicador en falso.
- Si el tamaño de la cola es par, comience a extraer un par mientras n > 1. Además, mientras extrae estos pares, verifique su diferencia y disminuya n en 2, si su diferencia no es igual a 1, establezca el indicador en falso.
- Finalmente, marque la bandera, si es verdadera, significa que los elementos en la cola están ordenados por pares, de lo contrario no.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check if successive
// pair of numbers in the queue are
// consecutive or not
#include <bits/stdc++.h>
using namespace std;
// Function to check if elements are
// pairwise consecutive in queue
bool pairWiseConsecutive(queue<int> q)
{
// Fetching size of queue
int n = q.size();
// Pushing extra element to the queue
// which acts as marker
q.push(INT_MIN);
// Result flag
bool result = true;
// If number of elements in the
// queue is odd pop elements while
// its size is greater than 2.
// Else, pop elements while its
// size is greater than 1
if (n % 2 != 0) {
while (n > 2) {
int x = q.front();
q.pop();
q.push(x);
n--;
int y = q.front();
q.pop();
q.push(y);
n--;
if (abs(x - y) != 1) {
result = false;
}
}
// Popping the last element of queue
// and pushing it again.
// Also, popping the extra element
// that we have pushed as marker
q.push(q.front());
q.pop();
q.pop();
}
else {
while (n > 1) {
int x = q.front();
q.pop();
q.push(x);
n--;
int y = q.front();
q.pop();
q.push(y);
n--;
if (abs(x - y) != 1) {
result = false;
}
}
// popping the extra element that
// we have pushed as marker
q.pop();
}
return result;
}
// Driver program
int main()
{
// Pushing elements into the queue
queue<int> q;
q.push(4);
q.push(5);
q.push(-2);
q.push(-3);
q.push(11);
q.push(10);
q.push(5);
q.push(6);
q.push(8);
if (pairWiseConsecutive(q))
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
Java
import java.util.LinkedList;
import java.util.Queue;
// Java program to check if successive
// pair of numbers in the queue are
// consecutive or not
public class GFG {
// Function to check if elements are
// pairwise consecutive in queue
static boolean pairWiseConsecutive(Queue<Integer> q) {
// Fetching size of queue
int n = q.size();
// Pushing extra element to the queue
// which acts as marker
q.add(Integer.MAX_VALUE);
// Result flag
boolean result = true;
// If number of elements in the
// queue is odd pop elements while
// its size is greater than 2.
// Else, pop elements while its
// size is greater than 1
if (n % 2 != 0) {
while (n > 2) {
int x = q.peek();
q.remove();
q.add(x);
n--;
int y = q.peek();
q.remove();
q.add(y);
n--;
if (Math.abs(x - y) != 1) {
result = false;
}
}
// Popping the last element of queue
// and pushing it again.
// Also, popping the extra element
// that we have pushed as marker
q.add(q.peek());
q.remove();
q.remove();
} else {
while (n > 1) {
int x = q.peek();
q.remove();
q.add(x);
n--;
int y = q.peek();
q.remove();
q.add(y);
n--;
if (Math.abs(x - y) != 1) {
result = false;
}
}
// popping the extra element that
// we have pushed as marker
q.remove();
}
return result;
}
// Driver program
static public void main(String[] args) {
// Pushing elements into the queue
Queue<Integer> q = new LinkedList<>();
q.add(4);
q.add(5);
q.add(-2);
q.add(-3);
q.add(11);
q.add(10);
q.add(5);
q.add(6);
q.add(8);
if (pairWiseConsecutive(q)) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to check if successive
# pair of numbers in the queue are
# consecutive or not
import sys, queue
# Function to check if elements are
# pairwise consecutive in queue
def pairWiseConsecutive(q):
# Fetching size of queue
n = q.qsize()
# Pushing extra element to the
# queue which acts as marker
q.put(-sys.maxsize);
# Result flag
result = bool(True)
# If number of elements in the
# queue is odd pop elements while
# its size is greater than 2.
# Else, pop elements while its
# size is greater than 1
if (n % 2 != 0):
while (n > 2):
x = q.queue[0]
q.get()
q.put(x)
n -= 1
y = q.queue[0]
q.get()
q.put(y)
n -= 1
if (abs(x - y) != 1):
result = bool(False)
# Popping the last element of queue
# and pushing it again.
# Also, popping the extra element
# that we have pushed as marker
q.put(q.queue[0])
q.get()
q.get()
else:
while (n > 1):
x = q.queue[0]
q.get()
q.put(x)
n -= 1
y = q.queue[0]
q.get()
q.put(y)
n -= 1
if (abs(x - y) != 1):
result = bool(False)
# popping the extra element that
# we have pushed as marker
q.get()
return result
# Driver code
# Pushing elements into the queue
q = queue.Queue()
q.put(4)
q.put(5)
q.put(-2)
q.put(-3)
q.put(11)
q.put(10)
q.put(5)
q.put(6)
q.put(8)
if (bool(pairWiseConsecutive(q))):
print("Yes")
else:
print("No")
# This code is contributed by divyeshrabadiya07
C#
// C# program to check if successive
// pair of numbers in the queue are
// consecutive or not
using System;
using System.Collections.Generic;
class GFG
{
// Function to check if elements are
// pairwise consecutive in queue
static Boolean pairWiseConsecutive(Queue<int> q)
{
// Fetching size of queue
int n = q.Count;
// Pushing extra element to the queue
// which acts as marker
q.Enqueue(int.MaxValue);
// Result flag
Boolean result = true;
// If number of elements in the
// queue is odd pop elements while
// its size is greater than 2.
// Else, pop elements while its
// size is greater than 1
if (n % 2 != 0)
{
while (n > 2)
{
int x = q.Peek();
q.Dequeue();
q.Enqueue(x);
n--;
int y = q.Peek();
q.Dequeue();
q.Enqueue(y);
n--;
if (Math.Abs(x - y) != 1)
{
result = false;
}
}
// Popping the last element of queue
// and pushing it again.
// Also, popping the extra element
// that we have pushed as marker
q.Enqueue(q.Peek());
q.Dequeue();
q.Dequeue();
} else
{
while (n > 1)
{
int x = q.Peek();
q.Dequeue();
q.Enqueue(x);
n--;
int y = q.Peek();
q.Dequeue();
q.Enqueue(y);
n--;
if (Math.Abs(x - y) != 1)
{
result = false;
}
}
// popping the extra element that
// we have pushed as marker
q.Dequeue();
}
return result;
}
// Driver Code
static public void Main(String[] args)
{
// Pushing elements into the queue
Queue<int> q = new Queue<int>();
q.Enqueue(4);
q.Enqueue(5);
q.Enqueue(-2);
q.Enqueue(-3);
q.Enqueue(11);
q.Enqueue(10);
q.Enqueue(5);
q.Enqueue(6);
q.Enqueue(8);
if (pairWiseConsecutive(q))
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
// This code is contributed by Rajput-Ji
Producción:
Yes
Complejidad temporal: O(n)
Espacio auxiliar: O(1)