Dada una pila S y un número entero N , la tarea es insertar N en la parte inferior de la pila.
Ejemplos:
Entrada: N = 7
S = 1 <- (Superior)
2
3
4
5
Salida: 1 2 3 4 5 7Entrada: N = 17
S = 1 <- (Superior)
12
34
47
15
Salida: 1 12 34 47 15 17
Enfoque ingenuo: el enfoque más simple sería crear otra pila. Siga los pasos a continuación para resolver el problema:
- Inicialice una pila , digamos temp .
- Siga sacando de la pila S dada y empujando los elementos sacados a temp , hasta que la pila S se vacíe.
- Empuje N en la pila S .
- Ahora, siga extrayendo de la temperatura de la pila y empuje los elementos emergentes en la pila S , hasta que la temperatura de la pila se vacíe .
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 insert an element
// at the bottom of a given stack
void insertToBottom(stack<int> S, int N)
{
// Temporary stack
stack<int> temp;
// Iterate until S becomes empty
while (!S.empty()) {
// Push the top element of S
// into the stack temp
temp.push(S.top());
// Pop the top element of S
S.pop();
}
// Push N into the stack S
S.push(N);
// Iterate until temp becomes empty
while (!temp.empty()) {
// Push the top element of
// temp into the stack S
S.push(temp.top());
// Pop the top element of temp
temp.pop();
}
// Print the elements of S
while (!S.empty()) {
cout << S.top() << " ";
S.pop();
}
}
// Driver Code
int main()
{
// Input
stack<int> S;
S.push(5);
S.push(4);
S.push(3);
S.push(2);
S.push(1);
int N = 7;
insertToBottom(S, N);
return 0;
}
Java
// Java program for the above approach
import java.util.Stack;
class GFG{
// Function to insert an element
// at the bottom of a given stack
static void insertToBottom(Stack<Integer> S, int N)
{
// Temporary stack
Stack<Integer> temp = new Stack<>();
// Iterate until S becomes empty
while (!S.empty())
{
// Push the top element of S
// into the stack temp
temp.push(S.peek());
// Pop the top element of S
S.pop();
}
// Push N into the stack S
S.push(N);
// Iterate until temp becomes empty
while (!temp.empty())
{
// Push the top element of
// temp into the stack S
S.push(temp.peek());
// Pop the top element of temp
temp.pop();
}
// Print the elements of S
while (!S.empty())
{
System.out.print(S.peek() + " ");
S.pop();
}
}
// Driver code
public static void main(String[] args)
{
// Given Binary Tree
Stack<Integer> S = new Stack<>();
S.push(5);
S.push(4);
S.push(3);
S.push(2);
S.push(1);
int N = 7;
insertToBottom(S, N);
}
}
// This code is contributed by abhinavjain194
Python3
# Python3 program for the above approach # Function to insert an element # at the bottom of a given stack def insertToBottom(S, N): # Temporary stack temp = [] # Iterate until S becomes empty while (len(S) != 0): # Push the top element of S # into the stack temp temp.append(S[-1]) # Pop the top element of S S.pop() # Push N into the stack S S.append(N) # Iterate until temp becomes empty while (len(temp) != 0): # Push the top element of # temp into the stack S S.append(temp[-1]) # Pop the top element of temp temp.pop() # Print the elements of S while (len(S) != 0): print(S[-1], end = " ") S.pop() # Driver Code if __name__ == "__main__": # Input S = [] S.append(5) S.append(4) S.append(3) S.append(2) S.append(1) N = 7 insertToBottom(S, N) # This code is contributed by ukasp
C#
// C# program for the above approach
using System;
using System.Collections;
public class GFG {
// Function to insert an element
// at the bottom of a given stack
static void insertToBottom(Stack S, int N)
{
// Temporary stack
Stack temp = new Stack();
// Iterate until S becomes empty
while (S.Count != 0) {
// Push the top element of S
// into the stack temp
temp.Push(S.Peek());
// Pop the top element of S
S.Pop();
}
// Push N into the stack S
S.Push(N);
// Iterate until temp becomes empty
while (temp.Count != 0) {
// Push the top element of
// temp into the stack S
S.Push(temp.Peek());
// Pop the top element of temp
temp.Pop();
}
// Print the elements of S
while (S.Count != 0) {
Console.Write(S.Peek() + " ");
S.Pop();
}
}
// Driver code
static public void Main()
{
// Given Binary Tree
Stack S = new Stack();
S.Push(5);
S.Push(4);
S.Push(3);
S.Push(2);
S.Push(1);
int N = 7;
insertToBottom(S, N);
}
}
// This code is contributed by Dharanendra L V.
Javascript
<script>
// JavaScript program for the above approach
// Function to insert an element
// at the bottom of a given stack
function insertToBottom(S, N)
{
// Temporary stack
var temp = [];
// Iterate until S becomes empty
while (S.length!=0) {
// Push the top element of S
// into the stack temp
temp.push(S[S.length-1]);
// Pop the top element of S
S.pop();
}
// Push N into the stack S
S.push(N);
// Iterate until temp becomes empty
while (temp.length!=0) {
// Push the top element of
// temp into the stack S
S.push(temp[temp.length-1]);
// Pop the top element of temp
temp.pop();
}
// Print the elements of S
while (S.length!=0) {
document.write( S[S.length-1] + " ");
S.pop();
}
}
// Driver Code
// Input
var S = [];
S.push(5);
S.push(4);
S.push(3);
S.push(2);
S.push(1);
var N = 7;
insertToBottom(S, N);
</script>
Producción:
1 2 3 4 5 7
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Enfoque eficiente: en lugar de usar una pila temporal, la pila implícita se puede usar a través de la recursividad . Siga los pasos a continuación para resolver el problema:
- Defina una función de recursión que acepte la pila S y un número entero como parámetros y devuelva una pila.
- El caso base a considerar es si la pila está vacía . Para este escenario, inserte N en la pila y devuélvalo.
- De lo contrario, elimine el elemento superior de S y guárdelo en una variable, digamos X .
- Recurra de nuevo usando la nueva pila
- Empuje X en S .
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;
// Recursive function to use implicit stack
// to insert an element at the bottom of stack
stack<int> recur(stack<int> S, int N)
{
// If stack is empty
if (S.empty())
S.push(N);
else {
// Stores the top element
int X = S.top();
// Pop the top element
S.pop();
// Recurse with remaining elements
S = recur(S, N);
// Push the previous
// top element again
S.push(X);
}
return S;
}
// Function to insert an element
// at the bottom of stack
void insertToBottom(
stack<int> S, int N)
{
// Recursively insert
// N at the bottom of S
S = recur(S, N);
// Print the stack S
while (!S.empty()) {
cout << S.top() << " ";
S.pop();
}
}
// Driver Code
int main()
{
// Input
stack<int> S;
S.push(5);
S.push(4);
S.push(3);
S.push(2);
S.push(1);
int N = 7;
insertToBottom(S, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class Main
{
// Recursive function to use implicit stack
// to insert an element at the bottom of stack
static Stack<Integer> recur(Stack<Integer> S, int N)
{
// If stack is empty
if (S.size() == 0)
S.push(N);
else {
// Stores the top element
int X = S.peek();
// Pop the top element
S.pop();
// Recurse with remaining elements
S = recur(S, N);
// Push the previous
// top element again
S.push(X);
}
return S;
}
// Function to insert an element
// at the bottom of stack
static void insertToBottom(Stack<Integer> S, int N)
{
// Recursively insert
// N at the bottom of S
S = recur(S, N);
// Print the stack S
while (S.size() > 0) {
System.out.print(S.peek() + " ");
S.pop();
}
}
public static void main(String[] args) {
// Input
Stack<Integer> S = new Stack<Integer>();
S.push(5);
S.push(4);
S.push(3);
S.push(2);
S.push(1);
int N = 7;
insertToBottom(S, N);
}
}
// This code is contributed by mukesh07.
Python3
# Python3 program for the above approach # Recursive function to use implicit stack # to insert an element at the bottom of stack def recur(S, N): # If stack is empty if (len(S) == 0): S.append(N) else: # Stores the top element X = S[-1] # Pop the top element S.pop() # Recurse with remaining elements S = recur(S, N) # Push the previous # top element again S.append(X) return S # Function to insert an element # at the bottom of stack def insertToBottom(S, N): # Recursively insert # N at the bottom of S S = recur(S, N) # Print the stack S while (len(S) > 0): print(S.pop(), end = " ") # Driver code # Input S = [] S.append(5) S.append(4) S.append(3) S.append(2) S.append(1) N = 7 insertToBottom(S, N) # This code is contributed by avanitrachhadiya2155
C#
// C# program for the above approach
using System;
using System.Collections;
class GFG {
// Recursive function to use implicit stack
// to insert an element at the bottom of stack
static Stack recur(Stack S, int N)
{
// If stack is empty
if (S.Count == 0)
S.Push(N);
else {
// Stores the top element
int X = (int)S.Peek();
// Pop the top element
S.Pop();
// Recurse with remaining elements
S = recur(S, N);
// Push the previous
// top element again
S.Push(X);
}
return S;
}
// Function to insert an element
// at the bottom of stack
static void insertToBottom(Stack S, int N)
{
// Recursively insert
// N at the bottom of S
S = recur(S, N);
// Print the stack S
while (S.Count > 0) {
Console.Write((int)S.Peek() + " ");
S.Pop();
}
}
static void Main() {
// Input
Stack S = new Stack();
S.Push(5);
S.Push(4);
S.Push(3);
S.Push(2);
S.Push(1);
int N = 7;
insertToBottom(S, N);
}
}
// This code is contributed by divyesh072019.
Javascript
<script>
// Javascript program for the above approach
// Recursive function to use implicit stack
// to insert an element at the bottom of stack
function recur(S, N)
{
// If stack is empty
if (S.length == 0)
S.push(N);
else {
// Stores the top element
let X = S[S.length - 1];
// Pop the top element
S.pop();
// Recurse with remaining elements
S = recur(S, N);
// Push the previous
// top element again
S.push(X);
}
return S;
}
// Function to insert an element
// at the bottom of stack
function insertToBottom(S, N)
{
// Recursively insert
// N at the bottom of S
S = recur(S, N);
// Print the stack S
while (S.length > 0) {
document.write(S[S.length - 1] + " ");
S.pop();
}
}
// Input
let S = [];
S.push(5);
S.push(4);
S.push(3);
S.push(2);
S.push(1);
let N = 7;
insertToBottom(S, N);
// This code is contributed by suresh07.
</script>
Producción:
1 2 3 4 5 7
Complejidad temporal: O(N), donde N es el número total de elementos en la pila.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por anushikasethh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA