Dada una array binaria, donde 1 denota una operación push y 0 denota una operación pop en una pila o cola . La tarea es verificar si el posible conjunto de operaciones es válido o no.
Ejemplos:
Entrada: a[] = {1, 1, 0, 0, 1}
Salida: válida
Entrada: a[] = {1, 1, 0, 0, 0}
Salida: no válida
La tercera operación emergente no se puede realizar como la pila o la cola estará vacía en ese momento.
Un enfoque ingenuo será usar una pila o cola y realizar una operación de inserción cuando un elemento de array es 1, y realizar una operación emergente cuando un elemento de array es 0. Cuando hay que realizar una operación emergente, entonces el movimiento no es válido. si la pila o cola está vacía. Si podemos realizar todas las operaciones, entonces los movimientos son válidos.
Complejidad de tiempo : O (N), ya que usaremos un bucle para atravesar N veces, donde N es el número de elementos en la array.
Espacio auxiliar : O(N), ya que usaremos espacio adicional para la pila o la cola.
Un enfoque eficiente será contar la operación de inserción y reducirla cuando se realice una operación emergente. Si durante cualquier instancia, el recuento se vuelve inferior a 0, entonces el conjunto de operaciones no es válido.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to Check if moves in a stack
// or queue are possible or not
#include <bits/stdc++.h>
using namespace std;
// Function to check if
// operations are valid or not
bool check(int a[], int n)
{
// count number of push operations
int ones = 0;
// traverse in the array
for (int i = 0; i < n; i++) {
// push operation
if (a[i])
ones++;
// pop operation
else
ones--;
// if at any moment pop() operations
// exceeds the number of push operations
if (ones < 0)
return false;
}
return true;
}
// Driver Code
int main()
{
int a[] = { 1, 1, 0, 0, 1 };
int n = sizeof(a) / sizeof(a[0]);
if (check(a, n))
cout << "Valid";
else
cout << "Invalid";
}
Java
// Java program to Check if moves in a stack
// or queue are possible or not
public class GFG {
// Function to check if
// operations are valid or not
static boolean check(int a[], int n) {
// count number of push operations
int ones = 0;
// traverse in the array
for (int i = 0; i < n; i++) {
// push operation
if (a[i] ==1) {
ones++;
} // pop operation
else {
ones--;
}
// if at any moment pop() operations
// exceeds the number of push operations
if (ones < 0) {
return false;
}
}
return true;
}
// Driver Code
static public void main(String[] args) {
int a[] = {1, 1, 0, 0, 1};
int n = a.length;
if (check(a, n)) {
System.out.println("Valid");
} else {
System.out.println("Invalid");
}
}
}
// This code is contributed by Rajput-Ji
Python 3
# Python 3 program to Check if moves
# in a stack or queue are possible or not
# Function to check if
# operations are valid or not
def check(a, n):
# count number of push operations
ones = 0;
# traverse in the array
for i in range (0, n):
# push operation
if (a[i]):
ones = ones + 1;
# pop operation
else:
ones = ones - 1;
# if at any moment pop() operations
# exceeds the number of push operations
if (ones < 0):
return False;
return True;
# Driver Code
a = [ 1, 1, 0, 0, 1 ];
n = len(a);
if (check(a, n)):
print("Valid");
else:
print("Invalid");
# This code is contributed
# by Akanksha Rai
C#
using System;
// C# program to Check if moves in a stack
// or queue are possible or not
public class GFG {
// Function to check if
// operations are valid or not
static bool check(int []a, int n) {
// count number of push operations
int ones = 0;
// traverse in the array
for (int i = 0; i < n; i++) {
// push operation
if (a[i] ==1) {
ones++;
} // pop operation
else {
ones--;
}
// if at any moment pop() operations
// exceeds the number of push operations
if (ones < 0) {
return false;
}
}
return true;
}
// Driver Code
static public void Main() {
int []a = {1, 1, 0, 0, 1};
int n = a.Length;
if (check(a, n)) {
Console.Write("Valid");
} else {
Console.Write("Invalid");
}
}
}
// This code is contributed by Rajput-Ji
PHP
<?php
// PHP program to Check if moves in a
// stack or queue are possible or not
// Function to check if
// operations are valid or not
function check($a, $n)
{
// count number of push operations
$ones = 0;
// traverse in the array
for ($i = 0; $i < $n; $i++)
{
// push operation
if ($a[$i])
$ones++;
// pop operation
else
$ones--;
// if at any moment pop() operations
// exceeds the number of push operations
if ($ones < 0)
return false;
}
return true;
}
// Driver Code
$a = array( 1, 1, 0, 0, 1 );
$n = count($a);
if (check($a, $n))
echo "Valid";
else
echo "Invalid";
// This code is contributed by Ryuga
?>
Javascript
<script>
// JavaScript program to Check if moves in a stack
// or queue are possible or not
// Function to check if
// operations are valid or not
function check(a , n) {
// count number of push operations
var ones = 0;
// traverse in the array
for (i = 0; i < n; i++) {
// push operation
if (a[i] == 1) {
ones++;
} // pop operation
else {
ones--;
}
// if at any moment pop() operations
// exceeds the number of push operations
if (ones < 0) {
return false;
}
}
return true;
}
// Driver Code
var a = [ 1, 1, 0, 0, 1 ];
var n = a.length;
if (check(a, n)) {
document.write("Valid");
} else {
document.write("Invalid");
}
// This code is contributed by todaysgaurav
</script>
Valid
Complejidad de tiempo : O (N), ya que estamos usando un ciclo para atravesar N veces, donde N es el número de elementos en la array.
Espacio auxiliar : O(1), ya que no estamos utilizando ningún espacio adicional.