Clone a stack without extra space
Given a source stack, copy the contents of the source stack to the destination stack maintaining the same order without using extra space.
Examples:
Input : Source:- |3|
|2|
|1|
Output : Destination:- |3|
|2|
|1|
Input : Source:- |a|
|b|
|c|
Output : Destination:- |a|
|b|
|c|
Approach:
In order to solve this without using extra space, we first reverse the source stack, then pop the top elements of the source stack one by one and push it into the destination stack. We follow the below steps to reverse the source stack:
- Initialize a variable count to 0.
- Pop the top element from the source stack and store it in variable topVal.
- Now pop the elements from the source stack and push them into the dest stack until the length of the source stack is equal to count.
- Push topVal into the source stack and then pop all the elements in the dest stack and push them into the source stack.
- Increment the value of count.
- If count is not equal to length of source stack – 1, repeat the process from step-2.
Below is the implementation of the above approach:
C++14
// C++ program to copy the contents from source stack // into destination stack without using extra space #include <iostream> #include <vector> using namespace std; // Define a class for Stack class Stack { vector< int > stack; public : void push( int value) { stack.push_back(value); } int pop() { int topVal = stack.back(); stack.pop_back(); return topVal; } int length() { return stack.size(); } void display() { for ( int i = stack.size() - 1; i >= 0; i--) { cout << stack[i] << endl; } cout << endl; } }; int main() { Stack source, dest; // Source Stack and Destination Stack source.push(1); source.push(2); source.push(3); cout << "Source Stack:" << endl; source.display(); int count = 0; // Reverse the order of the values in source stack while (count != source.length() - 1) { int topVal = source.pop(); while (count != source.length()) { dest.push(source.pop()); } source.push(topVal); while (dest.length() != 0) { source.push(dest.pop()); } count += 1; } // Pop the values from source and push into destination stack while (source.length() != 0) { dest.push(source.pop()); } cout << "Destination Stack:" << endl; dest.display(); return 0; } // This code is contributed by Pushpesh Raj. |
Java
import java.util.*; // Define a class for Stack class Stack { private List<Integer> stack = new ArrayList<>(); public void push( int value) { stack.add(value); } public int pop() { int topVal = stack.get(stack.size() - 1 ); stack.remove(stack.size() - 1 ); return topVal; } public int length() { return stack.size(); } public void display() { for ( int i = stack.size() - 1 ; i >= 0 ; i--) { System.out.println(stack.get(i)); } System.out.println(); } } public class Main { public static void main(String[] args) { Stack source = new Stack(); // Source Stack Stack dest = new Stack(); // Destination Stack source.push( 1 ); source.push( 2 ); source.push( 3 ); System.out.println( "Source Stack:" ); source.display(); int count = 0 ; // Reverse the order of the values in source stack while (count != source.length() - 1 ) { int topVal = source.pop(); while (count != source.length()) { dest.push(source.pop()); } source.push(topVal); while (dest.length() != 0 ) { source.push(dest.pop()); } count += 1 ; } // Pop the values from source and push into destination stack while (source.length() != 0 ) { dest.push(source.pop()); } System.out.println( "Destination Stack:" ); dest.display(); } } |
Python3
# Python3 program to copy the contents from source stack # into destination stack without using extra space # Define a class for Stack class Stack( object ): def __init__( self ): self .stack = [] def push( self , value): self .stack.append(value) def pop( self ): return self .stack.pop() def length( self ): return len ( self .stack) def display( self ): for i in range ( len ( self .stack) - 1 , - 1 , - 1 ): print ( self .stack[i]) print () source = Stack() # Source Stack dest = Stack() # Destination Stack source.push( 1 ) source.push( 2 ) source.push( 3 ) print ( "Source Stack:" ) source.display() count = 0 # Reverse the order of the values in source stack while count ! = source.length() - 1 : topVal = source.pop() while count ! = source.length(): dest.push(source.pop()) source.push(topVal) while dest.length() ! = 0 : source.push(dest.pop()) count + = 1 # Pop the values from source and push into destination stack while source.length() ! = 0 : dest.push(source.pop()) print ( "Destination Stack:" ) dest.display() |
C#
using System; using System.Collections.Generic; class Stack { private List< int > stack = new List< int >(); public void Push( int value) { stack.Add(value); } public int Pop() { int topVal = stack[stack.Count - 1]; stack.RemoveAt(stack.Count - 1); return topVal; } public int Length() { return stack.Count; } public void Display() { for ( int i = stack.Count - 1; i >= 0; i--) { Console.WriteLine(stack[i]); } Console.WriteLine(); } } class Program { static void Main( string [] args) { Stack source = new Stack(); // Source Stack Stack dest = new Stack(); // Destination Stack source.Push(1); source.Push(2); source.Push(3); Console.WriteLine( "Source Stack:" ); source.Display(); int count = 0; // Reverse the order of the values in source stack while (count != source.Length() - 1) { int topVal = source.Pop(); while (count != source.Length()) { dest.Push(source.Pop()); } source.Push(topVal); while (dest.Length() != 0) { source.Push(dest.Pop()); } count += 1; } // Pop the values from source and push into destination stack while (source.Length() != 0) { dest.Push(source.Pop()); } Console.WriteLine( "Destination Stack:" ); dest.Display(); } } |
Javascript
// JavaScript program to copy the contents from source stack // into destination stack without using extra space // Define a class for Stack class Stack { constructor() { this .stack = []; } push(value) { this .stack.push(value); } pop() { return this .stack.pop(); } length() { return this .stack.length; } display() { for (let i = this .stack.length - 1; i >= 0; i--) { console.log( this .stack[i]); } console.log(); } } const source = new Stack(); // Source Stack const dest = new Stack(); // Destination Stack source.push(1); source.push(2); source.push(3); console.log( "Source Stack:" ); source.display(); let count = 0; // Reverse the order of the values in source stack while (count !== source.length() - 1) { const topVal = source.pop(); while (count !== source.length()) { dest.push(source.pop()); } source.push(topVal); while (dest.length() !== 0) { source.push(dest.pop()); } count++; } // Pop the values from source and push into destination stack while (source.length() !== 0) { dest.push(source.pop()); } console.log( "Destination Stack:" ); dest.display(); |
Source Stack: 3 2 1 Destination Stack: 3 2 1
Complexity Analysis:
- Time Complexity: O(n2)
- Auxiliary Space: O(n)
Efficient Approach: A better approach would be to represent the stack as a linked list. Reverse the source stack in the same way we reverse a linked list, pop the top elements of the source stack one by one and push it into the destination stack.
Below is the implementation of the above approach:
C++
// c++ program to copy the contents from source stack // into destination stack without using extra space // in linear time using Linked List #include <iostream> using namespace std; // Class for StackNode to represent a node in the Stack class StackNode { public : int data; StackNode* next; StackNode( int val) { data = val; next = NULL; } }; // Class for Stack to represent it as Linked list class Stack { public : StackNode* top; Stack() { top = NULL; } void push( int value) { StackNode* newVal = new StackNode(value); if (top == NULL) { top = newVal; } else { newVal->next = top; top = newVal; } } int pop() { int val = top->data; top = top->next; return val; } void display() { StackNode* current = top; while (current != NULL) { cout << current->data << endl; current = current->next; } cout << endl; } void reverse() { StackNode* current = top; StackNode* temp = NULL; StackNode* prev = NULL; while (current != NULL) { temp = current->next; current->next = prev; prev = current; current = temp; } top = prev; } bool isEmpty() { return top == NULL; } }; int main() { Stack source; // Source Stack Stack dest; // Destination Stacksource.push(1); source.push(1); source.push(2); source.push(3); cout << "Source Stack:" << endl; source.display(); source.reverse(); // Pop the values from source and push into destination // stack while (source.isEmpty() != true ) { dest.push(source.pop()); } cout << "Destination Stack:" << endl; dest.display(); return 0; } |
Java
// Java program to copy the contents from source stack // into destination stack without using extra space // in linear time using Linked List class StackNode { public int data; public StackNode next; public StackNode( int val) { data = val; next = null ; } } class Stack { public StackNode top; public Stack() { top = null ; } public void push( int value) { StackNode newVal = new StackNode(value); if (top == null ) { top = newVal; } else { newVal.next = top; top = newVal; } } public int pop() { int val = top.data; top = top.next; return val; } public void display() { StackNode current = top; while (current != null ) { System.out.println(current.data); current = current.next; } System.out.println(); } public void reverse() { StackNode current = top; StackNode temp = null ; StackNode prev = null ; while (current != null ) { temp = current.next; current.next = prev; prev = current; current = temp; } top = prev; } public boolean isEmpty() { return top == null ; } } public class Main { public static void main(String[] args) { Stack source = new Stack(); // Source Stack Stack dest = new Stack(); // Destination Stack source.push( 1 ); source.push( 2 ); source.push( 3 ); System.out.println( "Source Stack:" ); source.display(); source.reverse(); // Pop the values from source and push into destination stack while (source.isEmpty() != true ) { dest.push(source.pop()); } System.out.println( "Destination Stack:" ); dest.display(); } } |
Python3
# Python3 program to copy the contents from source stack # into destination stack without using extra space # in linear time using Linked List class StackNode( object ): def __init__( self , data): self .data = data self . next = None # Class for Stack to represent it as Linked list class Stack( object ): def __init__( self ): self .top = None def push( self , value): newVal = StackNode(value) if self .top = = None : self .top = newVal else : newVal. next = self .top self .top = newVal def pop( self ): val = self .top.data self .top = self .top. next return val def display( self ): current = self .top while current ! = None : print (current.data) current = current. next print () def reverse( self ): current, temp, prev = self .top, None , None while current ! = None : temp = current. next current. next = prev prev = current current = temp self .top = prev def isEmpty( self ): return self .top = = None source = Stack() # Source Stack dest = Stack() # Destination Stack source.push( 1 ) source.push( 2 ) source.push( 3 ) print ( "Source Stack:" ) source.display() source.reverse() # Pop the values from source and push into destination stack while source.isEmpty() ! = True : dest.push(source.pop()) print ( "Destination Stack:" ) dest.display() |
C#
using System; // Class for StackNode to represent a node in the Stack class StackNode { public int data; public StackNode next; public StackNode( int val) { data = val; next = null ; } } // Class for Stack to represent it as Linked list class Stack { public StackNode top; public Stack() { top = null ; } public void Push( int value) { StackNode newVal = new StackNode(value); if (top == null ) { top = newVal; } else { newVal.next = top; top = newVal; } } public int Pop() { int val = top.data; top = top.next; return val; } public void Display() { StackNode current = top; while (current != null ) { Console.WriteLine(current.data); current = current.next; } Console.WriteLine(); } public void Reverse() { StackNode current = top; StackNode temp = null ; StackNode prev = null ; while (current != null ) { temp = current.next; current.next = prev; prev = current; current = temp; } top = prev; } public bool IsEmpty() { return top == null ; } } class GFG { static void Main( string [] args) { Stack source = new Stack(); // Source Stack Stack dest = new Stack(); // Destination Stack source.Push(1); source.Push(2); source.Push(3); Console.WriteLine( "Source Stack:" ); source.Display(); source.Reverse(); // Pop the values from source and push into destination // stack while (source.IsEmpty() != true ) { dest.Push(source.Pop()); } Console.WriteLine( "Destination Stack:" ); dest.Display(); Console.ReadLine(); } } |
Javascript
// JavaScript program to copy the contents from source stack // into destination stack without using extra space // in linear time using Linked List class StackNode { constructor(data) { this .data = data; this .next = null ; } } // Class for Stack to represent it as Linked list class Stack { constructor() { this .top = null ; } push(value) { let newVal = new StackNode(value); if ( this .top == null ) { this .top = newVal; } else { newVal.next = this .top; this .top = newVal; } } pop() { let val = this .top.data; this .top = this .top.next; return val; } display() { let current = this .top; while (current != null ) { console.log(current.data); current = current.next; } console.log(); } reverse() { let current = this .top; let temp = null ; let prev = null ; while (current != null ) { temp = current.next; current.next = prev; prev = current; current = temp; } this .top = prev; } isEmpty() { return this .top == null ; } } let source = new Stack(); // Source Stack let dest = new Stack(); // Destination Stack source.push(1); source.push(2); source.push(3); console.log( "Source Stack:" ); source.display(); source.reverse(); // Pop the values from source and push into destination stack while (source.isEmpty() !== true ) { dest.push(source.pop()); } console.log( "Destination Stack:" ); dest.display(); |
Source Stack: 3 2 1 Destination Stack: 3 2 1
Complexity Analysis:
- Time Complexity: O(n)
- Auxiliary Space: O(n)
ANOTHER APPROACH USING BUILT-IN LIBRARIES:
Intuition:
- The code is very simple and clear to understand.
- In the question ,two stack references were passed ,original stack and cloned stack.
- We keep a track of pop element from the original stack and again send the remaining stack in recursion until the size is 0
- Then we add it in the cloned stack.
Implementation:
C++
#include <iostream> #include <stack> void clonestack(std::stack< int >& st, std::stack< int >& cloned) { // If the source stack is empty, return. if (st.empty()) return ; // Pop an element from the source stack. int temp = st.top(); st.pop(); // Recursively clone the remaining elements. clonestack(st, cloned); // Push the popped element to the cloned stack. cloned.push(temp); } int main() { // Create the source stack and push elements onto it. std::stack< int > st; st.push(3); st.push(2); st.push(1); // Create an empty stack for cloning. std::stack< int > cloned; // Clone the source stack. clonestack(st, cloned); // Display the cloned stack. std::cout << "Destination Stack :\n" ; while (!cloned.empty()) { std::cout << cloned.top() << std::endl; cloned.pop(); } return 0; } // This code is contributed by shivamgupta310570 |
Java
// Java program to clone a stack without using extra space import java.io.*; import java.util.*; class GFG { static void clonestack(Stack<Integer> st, Stack<Integer> cloned) { // code here if (st.size() == 0 ) return ; int temp = st.pop(); clonestack(st, cloned); cloned.push(temp); } public static void main(String args[]) { Stack<Integer> st = new Stack<>(); st.push( 3 ); st.push( 2 ); st.push( 1 ); Stack<Integer> cloned = new Stack<>(); clonestack(st, cloned); System.out.println( "Destination Stack :" ); while (!cloned.isEmpty()) System.out.println(cloned.pop()); } } // This code is contributed by Raunak Singh |
Python3
class Stack: def __init__( self ): # Initialize an empty list to store stack items self .items = [] def isEmpty( self ): # Check if the stack is empty return len ( self .items) = = 0 def push( self , item): # Add an item to the stack self .items.append(item) def pop( self ): # Remove and return the top item from the stack if not self .isEmpty(): return self .items.pop() else : return None # Return None if the stack is empty def clonestack(st, cloned): # Recursive function to clone the stack if st.isEmpty(): return # Base case: If the original stack is empty, return temp = st.pop() # Remove the top item from the original stack clonestack(st, cloned) # Recursively clone the remaining elements cloned.push(temp) # Push the removed item to the cloned stack if __name__ = = "__main__" : st = Stack() st.push( 3 ) st.push( 2 ) st.push( 1 ) cloned = Stack() # Create an empty stack for the cloned items clonestack(st, cloned) # Clone the stack print ( "Destination Stack:" ) while not cloned.isEmpty(): # Display the cloned stack by popping and printing its items print (cloned.pop()) |
C#
// C# program to clone a stack without using extra space using System; using System.Collections.Generic; class GFG { static void CloneStack(Stack< int > st, Stack< int > cloned) { if (st.Count == 0) return ; int temp = st.Pop(); CloneStack(st, cloned); cloned.Push(temp); } public static void Main( string [] args) { Stack< int > st = new Stack< int >(); st.Push(3); st.Push(2); st.Push(1); Stack< int > cloned = new Stack< int >(); CloneStack(st, cloned); Console.WriteLine( "Destination Stack :" ); while (cloned.Count > 0) Console.WriteLine(cloned.Pop()); } } |
Javascript
class Stack { constructor() { // Initializing stack as an array and top as 0 this .items = []; this .top = 0; } // Push element onto the stack push(element) { this .items[ this .top] = element; this .top++; } // Pop element from the stack pop() { if ( this .isEmpty()) return "Underflow" ; this .top--; return this .items.pop(); } // Check if the stack is empty isEmpty() { return this .top === 0; } // Clone the stack without extra space cloneStack(cloned) { if ( this .isEmpty()) return ; // Remove top element from the original stack const temp = this .pop(); // Recursively clone the remaining stack elements this .cloneStack(cloned); // Preserve order by pushing the elements back to the original stack cloned.push(temp); this .push(temp); } // Print the stack elements printStack() { let top = this .top - 1; console.log( "Destination Stack:" ); while (top >= 0) { console.log( this .items[top]); top--; } } } // Example usage const st = new Stack(); st.push(3); st.push(2); st.push(1); const cloned = new Stack(); st.cloneStack(cloned); cloned.printStack(); |
Destination Stack : 1 2 3
Time Complexity: O(N)
Auxiliary Space: O(N) since we are not using any extra space apart from the stack that were passed as references in the question itself.