Dada una pila de enteros, escriba una función pairWiseSorted() que verifique si los números en la pila están ordenados por pares o no.
Los pares deben ser crecientes, y si la pila tiene un número impar de elementos, el elemento en la parte superior queda fuera de un par. La función debe conservar el contenido de la pila original.
Solo se permiten las siguientes operaciones estándar en la pila.
- empujar (X): ingrese un elemento X en la parte superior de la pila.
- pop(): elimina el elemento superior de la pila.
- vacío(): para comprobar si la pila está vacía.
Ejemplos:
Input: 4, 5, 6, 7, 8, 9 Output: Yes Input: 4, 9, 2, 1, 10, 8 Output: No
Enfoque: La idea es usar otra pila.
- Cree una pila auxiliar aux.
- Transfiere el contenido de la pila dada a aux.
- Travesaño auxiliar. Mientras se desplaza, busque los dos elementos superiores y compruebe si están ordenados o no.
- Después de verificar, vuelva a colocar estos elementos en la pila original.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check if successive // pair of numbers in the stack are // sorted or not #include <bits/stdc++.h> using namespace std; // Function to check if elements are // pairwise sorted in stack bool pairWiseConsecutive(stack<int> s) { // Transfer elements of s to aux. stack<int> aux; while (!s.empty()) { aux.push(s.top()); s.pop(); } // Traverse aux and see if // elements are pairwise // sorted or not. We also // need to make sure that original // content is retained. bool result = true; while (!aux.empty()) { // Fetch current top two // elements of aux and check // if they are sorted. int x = aux.top(); aux.pop(); int y = aux.top(); aux.pop(); if (x > y) result = false; // Push the elements to original // stack. s.push(x); s.push(y); } if (aux.size() == 1) s.push(aux.top()); return result; } // Driver program int main() { stack<int> s; s.push(4); s.push(5); s.push(-3); s.push(-2); s.push(10); s.push(11); s.push(5); s.push(6); // s.push(20); if (pairWiseConsecutive(s)) cout << "Yes" << endl; else cout << "No" << endl; cout << "Stack content (from top)" " after function call\n"; while (s.empty() == false) { cout << s.top() << " "; s.pop(); } return 0; }
Java
// Java program to check if successive // pair of numbers in the stack are // sorted or not import java.util.Stack; class GFG { // Function to check if elements are // pairwise sorted in stack static boolean pairWiseConsecutive(Stack<Integer> s) { // Transfer elements of s to aux. Stack<Integer> aux = new Stack<>(); while (!s.empty()) { aux.push(s.peek()); s.pop(); } // Traverse aux and see if // elements are pairwise // sorted or not. We also // need to make sure that original // content is retained. boolean result = true; while (!aux.empty()) { // Fetch current top two // elements of aux and check // if they are sorted. int x = aux.peek(); aux.pop(); int y = aux.peek(); aux.pop(); if (x > y) { result = false; } // Push the elements to original // stack. s.push(x); s.push(y); } if (aux.size() == 1) { s.push(aux.peek()); } return result; } // Driver program public static void main(String[] args) { Stack<Integer> s = new Stack<>(); s.push(4); s.push(5); s.push(-3); s.push(-2); s.push(10); s.push(11); s.push(5); s.push(6); // s.push(20); if (pairWiseConsecutive(s)) { System.out.println("Yes"); } else { System.out.println("No"); } System.out.println("Stack content (from top)" + " after function call"); while (s.empty() == false) { System.out.print(s.peek() + " "); s.pop(); } } }
Python 3
# Python program to check if successive # pair of numbers in the stack are # sorted or not # using deque as stack from collections import deque # Function to check if elements are # pairwise sorted in stack def pairWiseConsecutive(s): # Transfer elements of s to aux. aux = deque() while len(s) > 0: aux.append(s.pop()) # Traverse aux and see if # elements are pairwise # sorted or not. We also # need to make sure that original # content is retained. result = True while len(aux) != 0: # Fetch current top two # elements of aux and check # if they are sorted. x = aux.pop() y = aux.pop() if x > y: result = False # Push the elements to original # stack. s.append(x) s.append(y) if len(aux) == 1: s.append(aux.pop()) return result # Driver Code if __name__ == "__main__": s = deque() s.append(4) s.append(5) s.append(-3) s.append(-2) s.append(10) s.append(11) s.append(5) s.append(6) if pairWiseConsecutive(s): print("Yes") else: print("No") print("Stack content (from top) after function call") while len(s) > 0: print(s.pop(), end=" ") # This code is contributed by # sanjeev2552
C#
// C# program to check if successive // pair of numbers in the stack are using System; using System.Collections.Generic; public class GFG{ // Function to check if elements are // pairwise sorted in stack static bool pairWiseConsecutive(Stack<int> s) { // Transfer elements of s to aux. Stack<int> aux = new Stack<int>(); while (!(s.Count==0)) { aux.Push(s.Peek()); s.Pop(); } // Traverse aux and see if // elements are pairwise // sorted or not. We also // need to make sure that original // content is retained. bool result = true; while (!(aux.Count==0)) { // Fetch current top two // elements of aux and check // if they are sorted. int x = aux.Peek(); aux.Pop(); int y = aux.Peek(); aux.Pop(); if (x > y) { result = false; } // Push the elements to original // stack. s.Push(x); s.Push(y); } if (aux.Count == 1) { s.Push(aux.Peek()); } return result; } // Driver program public static void Main() { Stack<int> s = new Stack<int>(); s.Push(4); s.Push(5); s.Push(-3); s.Push(-2); s.Push(10); s.Push(11); s.Push(5); s.Push(6); // s.push(20); if (pairWiseConsecutive(s)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } Console.WriteLine("Stack content (from top)" + " after function call"); while (!(s.Count == 0)) { Console.Write(s.Peek() + " "); s.Pop(); } } }
Javascript
<script> // JavaScript program to check if successive // pair of numbers in the stack are // sorted or not // Function to check if elements are // pairwise sorted in stack function pairWiseConsecutive(s) { // Transfer elements of s to aux. var aux = []; while (s.length!=0) { aux.push(s[s.length-1]); s.pop(); } // Traverse aux and see if // elements are pairwise // sorted or not. We also // need to make sure that original // content is retained. var result = true; while (aux.length!=0) { // Fetch current top two // elements of aux and check // if they are sorted. var x = aux[aux.length-1]; aux.pop(); var y = aux[aux.length-1]; aux.pop(); if (x > y) result = false; // Push the elements to original // stack. s.push(x); s.push(y); } if (aux.length == 1) s.push(aux[aux.length-1]); return result; } // Driver program var s = []; s.push(4); s.push(5); s.push(-3); s.push(-2); s.push(10); s.push(11); s.push(5); s.push(6); // s.push(20); if (pairWiseConsecutive(s)) document.write( "Yes" + "<br>"); else document.write( "No" + "<br>"); document.write( "Stack content (from top)"+ " after function call<br>"); while (s.length!=0) { document.write( s[s.length-1] + " "); s.pop(); } </script>
Producción:
Yes Stack content (from top) after function call 6 5 11 10 -2 -3 5 4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)