Dada una array de N elementos distintos donde los elementos están entre 1 y N, ambos inclusive, verifique si se puede ordenar en pila o no. Se dice que una array A[] se puede ordenar en pilas si se puede almacenar en otra array B[], usando una pila temporal S.
Las operaciones que están permitidas en la array son:
- Retire el elemento inicial de la array A[] y empújelo a la pila.
- Retire el elemento superior de la pila S y agréguelo al final de la array B.
Si todo el elemento de A[] se puede mover a B[] realizando estas operaciones de modo que la array B se ordene en orden ascendente, entonces la array A[] se puede ordenar en la pila.
Ejemplos:
Input : A[] = { 3, 2, 1 }
Output : YES
Explanation :
Step 1: Remove the starting element of array A[]
and push it in the stack S. ( Operation 1)
That makes A[] = { 2, 1 } ; Stack S = { 3 }
Step 2: Operation 1
That makes A[] = { 1 } Stack S = { 3, 2 }
Step 3: Operation 1
That makes A[] = {} Stack S = { 3, 2, 1 }
Step 4: Operation 2
That makes Stack S = { 3, 2 } B[] = { 1 }
Step 5: Operation 2
That makes Stack S = { 3 } B[] = { 1, 2 }
Step 6: Operation 2
That makes Stack S = {} B[] = { 1, 2, 3 }
Input : A[] = { 2, 3, 1}
Output : NO
Dado, el arreglo A[] es una permutación de [1, …, N], así que supongamos que inicialmente B[] = {0}. Ahora podemos observar que:
- Solo podemos empujar un elemento en la pila S si la pila está vacía o si el elemento actual es menor que la parte superior de la pila.
- Solo podemos sacar de la pila solo si la parte superior de la pila es
![B[fin] + 1](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-47cda539e896bdb6d65b750c2119b430_l3.png "Procesado por QuickLaTeX.com")
como la array B[] contendrá {1, 2, 3, 4, …, n}.
Si no podemos empujar el elemento inicial de la array A[], entonces la array dada no se puede ordenar por pila.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ implementation of above approach.
#include <bits/stdc++.h>
using namespace std;
// Function to check if A[] is
// Stack Sortable or Not.
bool check(int A[], int N)
{
// Stack S
stack<int> S;
// Pointer to the end value of array B.
int B_end = 0;
// Traversing each element of A[] from starting
// Checking if there is a valid operation
// that can be performed.
for (int i = 0; i < N; i++)
{
// If the stack is not empty
if (!S.empty())
{
// Top of the Stack.
int top = S.top();
// If the top of the stack is
// Equal to B_end+1, we will pop it
// And increment B_end by 1.
while (top == B_end + 1)
{
// if current top is equal to
// B_end+1, we will increment
// B_end to B_end+1
B_end = B_end + 1;
// Pop the top element.
S.pop();
// If the stack is empty We cannot
// further perfom this operation.
// Therefore break
if (S.empty())
{
break;
}
// Current Top
top = S.top();
}
// If stack is empty
// Push the Current element
if (S.empty()) {
S.push(A[i]);
}
else
{
top = S.top();
// If the Current element of the array A[]
// if smaller than the top of the stack
// We can push it in the Stack.
if (A[i] < top)
{
S.push(A[i]);
}
// Else We cannot sort the array
// Using any valid operations.
else
{
// Not Stack Sortable
return false;
}
}
}
else
{
// If the stack is empty push the current
// element in the stack.
S.push(A[i]);
}
}
// Stack Sortable
return true;
}
// Driver's Code
int main()
{
int A[] = { 4, 1, 2, 3 };
int N = sizeof(A) / sizeof(A[0]);
check(A, N)? cout<<"YES": cout<<"NO";
return 0;
}
Java
// Java implementation of above approach.
import java.util.Stack;
class GFG {
// Function to check if A[] is
// Stack Sortable or Not.
static boolean check(int A[], int N) {
// Stack S
Stack<Integer> S = new Stack<Integer>();
// Pointer to the end value of array B.
int B_end = 0;
// Traversing each element of A[] from starting
// Checking if there is a valid operation
// that can be performed.
for (int i = 0; i < N; i++) {
// If the stack is not empty
if (!S.empty()) {
// Top of the Stack.
int top = S.peek();
// If the top of the stack is
// Equal to B_end+1, we will pop it
// And increment B_end by 1.
while (top == B_end + 1) {
// if current top is equal to
// B_end+1, we will increment
// B_end to B_end+1
B_end = B_end + 1;
// Pop the top element.
S.pop();
// If the stack is empty We cannot
// further perfom this operation.
// Therefore break
if (S.empty()) {
break;
}
// Current Top
top = S.peek();
}
// If stack is empty
// Push the Current element
if (S.empty()) {
S.push(A[i]);
} else {
top = S.peek();
// If the Current element of the array A[]
// if smaller than the top of the stack
// We can push it in the Stack.
if (A[i] < top) {
S.push(A[i]);
} // Else We cannot sort the array
// Using any valid operations.
else {
// Not Stack Sortable
return false;
}
}
} else {
// If the stack is empty push the current
// element in the stack.
S.push(A[i]);
}
}
// Stack Sortable
return true;
}
// Driver's Code
public static void main(String[] args) {
int A[] = {4, 1, 2, 3};
int N = A.length;
if (check(A, N)) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}
//This code is contributed by PrinciRaj1992
Python3
# Python implementation of above approach
def check(A, N):
# Stack S
S = []
# Pointer to the end value of array B.
B_end = 0
# Traversing each element of A[] from starting
# Checking if there is a valid operation
# that can be performed.
for i in range(N):
# if Stack is not empty
if len(S) != 0:
# top of the stack
top = S[-1]
# If the top of the stack is
# Equal to B_end+1, we will pop it
# And increment B_end by 1.
while top == B_end + 1:
# if current top is equal to
# B_end+1, we will increment
# B_end to B_end+1
B_end = B_end + 1
# Pop the top element
S.pop()
# If the stack is empty We cannot
# further perfom this operation.
# Therefore break
if len(S) == 0:
break
# Current top
top = S[-1]
# If stack is empty
# Push the Current element
if len(S) == 0:
S.append(A[i])
else:
top = S[-1]
# If the Current element of the array A[]
# if smaller than the top of the stack
# We can push it in the Stack.
if A[i] < top:
S.append(A[i])
# Else We cannot sort the array
# Using any valid operations.
else:
# Not Stack Sortable
return False
else:
# If the stack is empty push the current
# element in the stack.
S.append(A[i])
return True
# Driver's Function
if __name__ == "__main__":
A = [4, 1, 2, 3]
N = len(A)
if check(A, N):
print("YES")
else:
print("NO")
Producción:
YES
Complejidad temporal : O(N).