Dada una pila S y un entero K , la tarea es invertir los primeros K elementos de la pila dada
Ejemplos :
Entrada: S = [ 1, 2, 3, 4, 5, 8, 3, 0, 9 ], K = 4
Salida: [ 4, 3, 2, 1, 5, 8, 3, 0, 9 ]
Explicación : Los primeros 4 elementos de la pila dada se inviertenEntrada: S = [ 1, 2, 3, 4, 5, 8, 3, 0, 9 ], K= 7
Salida: [ 3, 8, 5, 4, 3, 2, 1, 0, 9 ]
Enfoque : la tarea se puede resolver usando dos pilas auxiliares para invertir los primeros K elementos de la pila dada. Siga los pasos a continuación para resolver el problema:
- Crea dos pilas s1 y s2
- Uno por uno, extraiga todos los elementos de la pila dada y empújelos simultáneamente a la pila s1
- Ahora, extraiga k cantidad de elementos de s1 y empújelos en s2 simultáneamente
- Extraiga todos los elementos de la pila s2 y empújelos a la pila dada
- De manera similar, extraiga todos los elementos de s1 y empújelos a la pila dada
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the resultant stack
void print(stack<int>& s)
{
vector<int> v;
while (!s.empty()) {
int temp = s.top();
s.pop();
v.push_back(temp);
}
reverse(v.begin(), v.end());
for (int i = 0; i < v.size(); i++)
cout << " " << v[i] << " ";
}
// Function to reverse and push operation
// in the stack
void stack_reverse(stack<int>& s, int k)
{
stack<int> s1, s2;
while (!s.empty()) {
int temp = s.top();
s1.push(temp);
s.pop();
}
for (int i = 0; i < k; i++) {
int temp = s1.top();
s2.push(temp);
s1.pop();
}
while (!s2.empty()) {
int temp = s2.top();
s.push(temp);
s2.pop();
}
while (!s1.empty()) {
int temp = s1.top();
s.push(temp);
s1.pop();
}
}
// Driver Code
int main()
{
stack<int> s;
// s = [ 1, 2, 3, 4, 5, 8, 3, 0, 9 ]
s.push(1);
s.push(2);
s.push(3);
s.push(4);
s.push(5);
s.push(8);
s.push(3);
s.push(0);
s.push(9);
int k = 4;
stack_reverse(s, k);
print(s);
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
static Stack<Integer> s = new Stack<>();
// Function to print the resultant stack
static void print()
{
Vector<Integer> v = new Vector<>();
while (!s.isEmpty()) {
int temp = s.peek();
s.pop();
v.add(temp);
}
Collections.reverse(v);
for (int i = 0; i < v.size(); i++)
System.out.print(" " + v.get(i)+ " ");
}
// Function to reverse and push operation
// in the stack
static void stack_reverse(int k)
{
Stack<Integer> s1 = new Stack<>(), s2 =new Stack<>();
while (!s.isEmpty()) {
int temp = s.peek();
s1.add(temp);
s.pop();
}
for (int i = 0; i < k; i++) {
int temp = s1.peek();
s2.add(temp);
s1.pop();
}
while (!s2.isEmpty()) {
int temp = s2.peek();
s.add(temp);
s2.pop();
}
while (!s1.isEmpty()) {
int temp = s1.peek();
s.add(temp);
s1.pop();
}
}
// Driver Code
public static void main(String[] args)
{
// s = [ 1, 2, 3, 4, 5, 8, 3, 0, 9 ]
s.add(1);
s.add(2);
s.add(3);
s.add(4);
s.add(5);
s.add(8);
s.add(3);
s.add(0);
s.add(9);
int k = 4;
stack_reverse(k);
print();
}
}
// This code is contributed by gauravrajput1
Python3
# python3 program for the above approach
# Function to print the resultant stack
def print(s):
v = []
while (len(s) != 0):
temp = s.pop()
v.append(temp)
v.reverse()
for i in range(0, len(v)):
print(f" {v[i]} ", end="")
# Function to reverse and push operation
# in the stack
def stack_reverse(s, k):
s1, s2 = [], []
while (len(s) != 0):
temp = s.pop()
s1.append(temp)
for i in range(0, k):
temp = s1.pop()
s2.append(temp)
while (len(s2) != 0):
temp = s2.pop()
s.append(temp)
while (len(s1) != 0):
temp = s1.pop()
s.append(temp)
# Driver Code
if __name__ == "__main__":
s = []
# s = [ 1, 2, 3, 4, 5, 8, 3, 0, 9 ]
s.append(1)
s.append(2)
s.append(3)
s.append(4)
s.append(5)
s.append(8)
s.append(3)
s.append(0)
s.append(9)
k = 4
stack_reverse(s, k)
print(s)
# This code is contributed by rakeshsahni
Javascript
<script>
// JavaScript code for the above approach
// Function to print the resultant stack
function print(s) {
let v = [];
while (s.length != 0) {
let temp = s[s.length - 1];
s.pop();
v.push(temp);
}
v.reverse();
for (let i = 0; i < v.length; i++)
document.write(" " + v[i] + " ");
}
// Function to reverse and push operation
// in the stack
function stack_reverse(s, k) {
let s1 = [], s2 = [];
while (s.length != 0) {
let temp = s[s.length - 1];
s1.push(temp);
s.pop();
}
for (let i = 0; i < k; i++) {
let temp = s1[s1.length - 1];
s2.push(temp);
s1.pop();
}
while (s2.length != 0) {
let temp = s2[s2.length - 1];
s.push(temp);
s2.pop();
}
while (s1.length != 0) {
let temp = s1[s1.length - 1];
s.push(temp);
s1.pop();
}
}
// Driver Code
let s = [];
// s = [ 1, 2, 3, 4, 5, 8, 3, 0, 9 ]
s.push(1);
s.push(2);
s.push(3);
s.push(4);
s.push(5);
s.push(8);
s.push(3);
s.push(0);
s.push(9);
let k = 4;
stack_reverse(s, k);
print(s);
// This code is contributed by Potta Lokesh
</script>
Producción
4 3 2 1 5 8 3 0 9
Complejidad de tiempo : O(N), N es el número de elementos en la pila
Espacio auxiliar : O(N)