Implement two Stacks in an Array

Last Updated : 13 Jul, 2023

Create a data structure twoStacks that represent two stacks. Implementation of twoStacks should use only one array, i.e., both stacks should use the same array for storing elements.

Following functions must be supported by twoStacks.

push1(int x) –> pushes x to first stack

push2(int x) –> pushes x to second stack

pop1() –> pops an element from first stack and return the popped element

pop2() –> pops an element from second stack and return the popped element

Implementation of twoStack should be space efficient.

Implement two stacks in an array by Dividing the space into two halves:

The idea to implement two stacks is to divide the array into two halves and assign two halves to two stacks, i.e., use arr[0] to arr[n/2] for stack1, and arr[(n/2) + 1] to arr[n-1] for stack2 where arr[] is the array to be used to implement two stacks and size of array be n.

Follow the steps below to solve the problem:

To implement push1():
- First, check whether the top1 is greater than 0
  - If it is then add an element at the top1 index and decrement top1 by 1
  - Else return Stack Overflow
To implement push2():
- First, check whether top2 is less than n – 1
  - If it is then add an element at the top2 index and increment the top2 by 1
  - Else return Stack Overflow
To implement pop1():
- First, check whether the top1 is less than or equal to n / 2
  - If it is then increment the top1 by 1 and return that element.
  - Else return Stack Underflow
To implement pop2():
- First, check whether the top2 is greater than or equal to (n + 1) / 2
  - If it is then decrement the top2 by 1 and return that element.
  - Else return Stack Underflow

Below is the implementation of the above approach.

C++

#include <bits/stdc++.h> 
using namespace std; 
  
class twoStacks { 
    int* arr; 
    int size; 
    int top1, top2; 
  
public: 
    // Constructor 
    twoStacks(int n) 
    { 
        size = n; 
        arr = new int[n]; 
        top1 = n / 2 + 1; 
        top2 = n / 2; 
    } 
  
    // Method to push an element x to stack1 
    void push1(int x) 
    { 
        // There is at least one empty 
        // space for new element 
        if (top1 > 0) { 
            top1--; 
            arr[top1] = x; 
        } 
        else { 
            cout << "Stack Overflow"
                 << " By element : " << x << endl; 
            return; 
        } 
    } 
  
    // Method to push an element 
    // x to stack2 
    void push2(int x) 
    { 
  
        // There is at least one empty 
        // space for new element 
        if (top2 < size - 1) { 
            top2++; 
            arr[top2] = x; 
        } 
        else { 
            cout << "Stack Overflow"
                 << " By element : " << x << endl; 
            return; 
        } 
    } 
  
    // Method to pop an element from first stack 
    int pop1() 
    { 
        if (top1 <= size / 2) { 
            int x = arr[top1]; 
            top1++; 
            return x; 
        } 
        else { 
            cout << "Stack UnderFlow"; 
            exit(1); 
        } 
    } 
  
    // Method to pop an element 
    // from second stack 
    int pop2() 
    { 
        if (top2 >= size / 2 + 1) { 
            int x = arr[top2]; 
            top2--; 
            return x; 
        } 
        else { 
            cout << "Stack UnderFlow" << endl; 
            exit(1); 
        } 
    } 
}; 
  
/* Driver program to test twoStacks class */
int main() 
{ 
    twoStacks ts(5); 
    ts.push1(5); 
    ts.push2(10); 
    ts.push2(15); 
    ts.push1(11); 
    ts.push2(7); 
    cout << "Popped element from stack1 is "
         << ": " << ts.pop1() << endl; 
    ts.push2(40); 
    cout << "Popped element from stack2 is "
         << ": " << ts.pop2() << endl; 
    return 0; 
}

Java

import java.util.*; 
  
class twoStacks { 
    int[] arr; 
    int size; 
    int top1, top2; 
  
    // Constructor 
    twoStacks(int n) 
    { 
        size = n; 
        arr = new int[n]; 
        top1 = n / 2 + 1; 
        top2 = n / 2; 
    } 
  
    // Method to push an element x to stack1 
    void push1(int x) 
    { 
  
        // There is at least one empty 
        // space for new element 
        if (top1 > 0) { 
            top1--; 
            arr[top1] = x; 
        } 
        else { 
            System.out.println("Stack Overflow"
                             + " By element : " + x); 
            return; 
        } 
    } 
  
    // Method to push an element 
    // x to stack2 
    void push2(int x) 
    { 
  
        // There is at least one empty 
        // space for new element 
        if (top2 < size - 1) { 
            top2++; 
            arr[top2] = x; 
        } 
        else { 
            System.out.println("Stack Overflow"
                             + " By element : " + x); 
            return; 
        } 
    } 
  
    // Method to pop an element from first stack 
    int pop1() 
    { 
        if (top1 <= size / 2) { 
            int x = arr[top1]; 
            top1++; 
            return x; 
        } 
        else { 
            System.out.print("Stack UnderFlow"); 
            System.exit(1); 
        } 
        return 0; 
    } 
  
    // Method to pop an element 
    // from second stack 
    int pop2() 
    { 
        if (top2 >= size / 2 + 1) { 
            int x = arr[top2]; 
            top2--; 
            return x; 
        } 
        else { 
            System.out.print("Stack UnderFlow"); 
            System.exit(1); 
        } 
        return 1; 
    } 
}; 
class GFG { 
  
    /* Driver program to test twoStacks class */
    public static void main(String[] args) 
    { 
        twoStacks ts = new twoStacks(5); 
        ts.push1(5); 
        ts.push2(10); 
        ts.push2(15); 
        ts.push1(11); 
        ts.push2(7); 
        System.out.println("Popped element from stack1 is "
                         + ": " + ts.pop1()); 
        ts.push2(40); 
        System.out.println("Popped element from stack2 is "
                         + ": " + ts.pop2()); 
    } 
} 
  
// This code is contributed by aashish1995

Python3

# Python Script to Implement two stacks in a list 
import math 
  
  
class twoStacks: 
  
    def __init__(self, n):     # constructor 
        self.size = n 
        self.arr = [None] * n 
        self.top1 = math.floor(n/2) + 1
        self.top2 = math.floor(n/2) 
  
    # Method to push an element x to stack1 
  
    def push1(self, x): 
  
        # There is at least one empty space for new element 
        if self.top1 > 0: 
            self.top1 = self.top1 - 1
            self.arr[self.top1] = x 
        else: 
            print("Stack Overflow by element : ", x) 
  
    # Method to push an element x to stack2 
  
    def push2(self, x): 
  
        # There is at least one empty space for new element 
        if self.top2 < self.size - 1: 
            self.top2 = self.top2 + 1
            self.arr[self.top2] = x 
        else: 
            print("Stack Overflow by element : ", x) 
  
    # Method to pop an element from first stack 
  
    def pop1(self): 
        if self.top1 <= self.size/2: 
            x = self.arr[self.top1] 
            self.top1 = self.top1 + 1
            return x 
        else: 
            print("Stack Underflow") 
            exit(1) 
  
    # Method to pop an element from second stack 
  
    def pop2(self): 
        if self.top2 >= math.floor(self.size/2) + 1: 
            x = self.arr[self.top2] 
            self.top2 = self.top2 - 1
            return x 
        else: 
            print("Stack Underflow") 
            exit(1) 
  
  
# Driver program to test twoStacks class 
if __name__ == '__main__': 
    ts = twoStacks(5) 
    ts.push1(5) 
    ts.push2(10) 
    ts.push2(15) 
    ts.push1(11) 
    ts.push2(7) 
      
    print("Popped element from stack1 is : " + str(ts.pop1())) 
    ts.push2(40) 
    print("Popped element from stack2 is : " + str(ts.pop2())) 
  
# This code is contributed by Gautam goel 

C#

using System; 
using System.Collections.Generic; 
  
public class twoStacks { 
    public int[] arr; 
    public int size; 
    public int top1, top2; 
  
    // Constructor 
    public twoStacks(int n) 
    { 
        size = n; 
        arr = new int[n]; 
        top1 = n / 2 + 1; 
        top2 = n / 2; 
    } 
  
    // Method to push an element x to stack1 
    public void push1(int x) 
    { 
  
        // There is at least one empty 
        // space for new element 
        if (top1 > 0) { 
            top1--; 
            arr[top1] = x; 
        } 
        else { 
            Console.Write("Stack Overflow"
                          + " By element : " + x + "\n"); 
            return; 
        } 
    } 
  
    // Method to push an element 
    // x to stack2 
    public void push2(int x) 
    { 
  
        // There is at least one empty 
        // space for new element 
        if (top2 < size - 1) { 
            top2++; 
            arr[top2] = x; 
        } 
        else { 
            Console.Write("Stack Overflow"
                          + " By element : " + x + "\n"); 
            return; 
        } 
    } 
  
    // Method to pop an element from first stack 
    public int pop1() 
    { 
        if (top1 <= size / 2) { 
            int x = arr[top1]; 
            top1++; 
            return x; 
        } 
        else { 
            Console.Write("Stack UnderFlow"); 
        } 
        return 0; 
    } 
  
    // Method to pop an element 
    // from second stack 
    public int pop2() 
    { 
        if (top2 >= size / 2 + 1) { 
            int x = arr[top2]; 
            top2--; 
            return x; 
        } 
        else { 
            Console.Write("Stack UnderFlow"); 
        } 
        return 1; 
    } 
}; 
  
public class GFG { 
  
    /* Driver program to test twoStacks class */
    public static void Main(String[] args) 
    { 
        twoStacks ts = new twoStacks(5); 
        ts.push1(5); 
        ts.push2(10); 
        ts.push2(15); 
        ts.push1(11); 
        ts.push2(7); 
        Console.Write("Popped element from stack1 is "
                      + ": " + ts.pop1() + "\n"); 
        ts.push2(40); 
        Console.Write("Popped element from stack2 is "
                      + ": " + ts.pop2() + "\n"); 
    } 
} 
  
// This code is contributed by umadevi9616

Javascript

<script> 
  
class twoStacks 
{ 
    // Constructor 
    constructor(n) 
    { 
        this.arr = new Array(n); 
        this.size = n; 
        this.top1 = Math.floor(n / 2) + 1; 
        this.top2 = Math.floor(n / 2);         
    } 
  
// Method to push an element x to stack1 
push1(x) 
{ 
    // There is at least one empty 
    // space for new element 
    if (this.top1 > 0) 
    { 
      this.top1--; 
      this.arr[this.top1] = x; 
    } 
    else
    { 
      document.write("Stack Overflow"
                       + " By element : " +  x +"<br>"); 
      return; 
    } 
} 
  
// Method to push an element 
  // x to stack2 
push2(x) 
{ 
    // There is at least one empty 
    // space for new element 
    if (this.top2 < this.size - 1) 
    { 
      this.top2++; 
      this.arr[this.top2] = x; 
    } 
    else
    { 
      document.write("Stack Overflow"
                       + " By element : " +  x +"<br>"); 
      return; 
    } 
} 
  
// Method to pop an element from first stack 
pop1() 
{ 
    if (this.top1 <= this.size / 2) 
    { 
      let x = this.arr[this.top1]; 
      this.top1++; 
      return x; 
    } 
    else
    { 
      document.write("Stack UnderFlow"); 
        
    } 
    return 0; 
} 
  
// Method to pop an element 
  // from second stack 
pop2() 
{ 
    if (this.top2 >= Math.floor(this.size / 2) + 1) 
    { 
      let x = this.arr[this.top2]; 
      this.top2--; 
      return x; 
    } 
    else
    { 
      document.write("Stack UnderFlow"); 
        
    } 
    return 1; 
  } 
  
} 
  
/* Driver program to test twoStacks class */
let ts = new twoStacks(5); 
ts.push1(5); 
ts.push2(10); 
ts.push2(15); 
ts.push1(11); 
ts.push2(7); 
document.write("Popped element from stack1 is "
                 + " : " +  ts.pop1() +"<br>"); 
ts.push2(40); 
document.write("Popped element from stack2 is "
                 + ": " +  ts.pop2() 
                 +"<br>"); 
  
// This code is contributed by avanitrachhadiya2155 
</script>

Output

Stack Overflow By element : 7
Popped element from stack1 is : 11
Stack Overflow By element : 40
Popped element from stack2 is : 15

Time Complexity:

Both Push operation: O(1)
Both Pop operation: O(1)

Auxiliary Space: O(N), Use of array to implement stack.

Problem in the above implementation:

The problem in the above implementation is that as we reserve half of the array for a stack and another half for the another stack. So, let if 1st half is full means first stack already have n/2 numbers of elements and 2nd half is not full means it doesn’t have n/2 numbers of elements. So, if we look into the array, there are free spaces inside array(eg. in the next half) but we cannot push elements for stack 1(because first half is reserved for stack 1 and it’s already full). It means this implementation show stack overflow although the array is not full. The solution for this answer is the below implementation.

Implement two stacks in an array by Starting from endpoints:

The idea is to start two stacks from two extreme corners of arr[].

Follow the steps below to solve the problem:

Stack1 starts from the leftmost corner of the array, the first element in stack1 is pushed at index 0 of the array.
Stack2 starts from the rightmost corner of the array, the first element in stack2 is pushed at index (n-1) of the array.
Both stacks grow (or shrink) in opposite directions.
To check for overflow, all we need to check is for availability of space between top elements of both stacks.
To check for underflow, all we need to check is if the value of the top of the both stacks is between 0 to (n-1) or not.

Below is the implementation of above approach:

C++

#include <iostream> 
#include <stdlib.h> 
  
using namespace std; 
  
class twoStacks { 
    int* arr; 
    int size; 
    int top1, top2; 
  
public: 
    twoStacks(int n) // constructor 
    { 
        size = n; 
        arr = new int[n]; 
        top1 = -1; 
        top2 = size; 
    } 
  
    // Method to push an element x to stack1 
    void push1(int x) 
    { 
        // There is at least one empty space for new element 
        if (top1 < top2 - 1) { 
            top1++; 
            arr[top1] = x; 
        } 
        else { 
            cout << "Stack Overflow"; 
            exit(1); 
        } 
    } 
  
    // Method to push an element x to stack2 
    void push2(int x) 
    { 
        // There is at least one empty 
        // space for new element 
        if (top1 < top2 - 1) { 
            top2--; 
            arr[top2] = x; 
        } 
        else { 
            cout << "Stack Overflow"; 
            exit(1); 
        } 
    } 
  
    // Method to pop an element from first stack 
    int pop1() 
    { 
        if (top1 >= 0) { 
            int x = arr[top1]; 
            top1--; 
            return x; 
        } 
        else { 
            cout << "Stack UnderFlow"; 
            exit(1); 
        } 
    } 
  
    // Method to pop an element from second stack 
    int pop2() 
    { 
        if (top2 < size) { 
            int x = arr[top2]; 
            top2++; 
            return x; 
        } 
        else { 
            cout << "Stack UnderFlow"; 
            exit(1); 
        } 
    } 
}; 
  
/* Driver program to test twoStacks class */
int main() 
{ 
    twoStacks ts(5); 
    ts.push1(5); 
    ts.push2(10); 
    ts.push2(15); 
    ts.push1(11); 
    ts.push2(7); 
    cout << "Popped element from stack1 is " << ts.pop1(); 
    ts.push2(40); 
    cout << "\nPopped element from stack2 is " << ts.pop2(); 
    return 0; 
}

Java

// Java program to implement two stacks in a 
// single array 
  
import java.io.*; 
  
class TwoStacks { 
    int size; 
    int top1, top2; 
    int arr[]; 
  
    // Constructor 
    TwoStacks(int n) 
    { 
        arr = new int[n]; 
        size = n; 
        top1 = -1; 
        top2 = size; 
    } 
  
    // Method to push an element x to stack1 
    void push1(int x) 
    { 
        // There is at least one empty space for 
        // new element 
        if (top1 < top2 - 1) { 
            top1++; 
            arr[top1] = x; 
        } 
        else { 
            System.out.println("Stack Overflow"); 
            System.exit(1); 
        } 
    } 
  
    // Method to push an element x to stack2 
    void push2(int x) 
    { 
        // There is at least one empty space for 
        // new element 
        if (top1 < top2 - 1) { 
            top2--; 
            arr[top2] = x; 
        } 
        else { 
            System.out.println("Stack Overflow"); 
            System.exit(1); 
        } 
    } 
  
    // Method to pop an element from first stack 
    int pop1() 
    { 
        if (top1 >= 0) { 
            int x = arr[top1]; 
            top1--; 
            return x; 
        } 
        else { 
            System.out.println("Stack Underflow"); 
            System.exit(1); 
        } 
        return 0; 
    } 
  
    // Method to pop an element from second stack 
    int pop2() 
    { 
        if (top2 < size) { 
            int x = arr[top2]; 
            top2++; 
            return x; 
        } 
        else { 
            System.out.println("Stack Underflow"); 
            System.exit(1); 
        } 
        return 0; 
    } 
  
    // Driver program to test twoStack class 
    public static void main(String args[]) 
    { 
        TwoStacks ts = new TwoStacks(5); 
        ts.push1(5); 
        ts.push2(10); 
        ts.push2(15); 
        ts.push1(11); 
        ts.push2(7); 
        System.out.println("Popped element from"
                           + " stack1 is " + ts.pop1()); 
        ts.push2(40); 
        System.out.println("Popped element from"
                           + " stack2 is " + ts.pop2()); 
    } 
} 
// This code has been contributed by 
// Amit Khandelwal(Amit Khandelwal 1).

Python

# Python Script to Implement two stacks in a list 
class twoStacks: 
  
    def __init__(self, n):     # constructor 
        self.size = n 
        self.arr = [None] * n 
        self.top1 = -1
        self.top2 = self.size 
  
    # Method to push an element x to stack1 
    def push1(self, x): 
  
        # There is at least one empty space for new element 
        if self.top1 < self.top2 - 1: 
            self.top1 = self.top1 + 1
            self.arr[self.top1] = x 
  
        else: 
            print("Stack Overflow ") 
            exit(1) 
  
    # Method to push an element x to stack2 
    def push2(self, x): 
  
        # There is at least one empty space for new element 
        if self.top1 < self.top2 - 1: 
            self.top2 = self.top2 - 1
            self.arr[self.top2] = x 
  
        else: 
            print("Stack Overflow ") 
            exit(1) 
  
    # Method to pop an element from first stack 
    def pop1(self): 
        if self.top1 >= 0: 
            x = self.arr[self.top1] 
            self.top1 = self.top1 - 1
            return x 
        else: 
            print("Stack Underflow ") 
            exit(1) 
  
    # Method to pop an element from second stack 
    def pop2(self): 
        if self.top2 < self.size: 
            x = self.arr[self.top2] 
            self.top2 = self.top2 + 1
            return x 
        else: 
            print("Stack Underflow ") 
            exit() 
  
  
# Driver program to test twoStacks class 
ts = twoStacks(5) 
ts.push1(5) 
ts.push2(10) 
ts.push2(15) 
ts.push1(11) 
ts.push2(7) 
  
print("Popped element from stack1 is " + str(ts.pop1())) 
ts.push2(40) 
print("Popped element from stack2 is " + str(ts.pop2())) 
  
# This code is contributed by Sunny Karira 

C#

// C# program to implement two 
// stacks in a single array 
using System; 
  
public class TwoStacks { 
    public int size; 
    public int top1, top2; 
    public int[] arr; 
  
    // Constructor 
    public TwoStacks(int n) 
    { 
        arr = new int[n]; 
        size = n; 
        top1 = -1; 
        top2 = size; 
    } 
  
    // Method to push an element x to stack1 
    public virtual void push1(int x) 
    { 
        // There is at least one empty 
        // space for new element 
        if (top1 < top2 - 1) { 
            top1++; 
            arr[top1] = x; 
        } 
        else { 
            Console.WriteLine("Stack Overflow"); 
            Environment.Exit(1); 
        } 
    } 
  
    // Method to push an element x to stack2 
    public virtual void push2(int x) 
    { 
        // There is at least one empty 
        // space for new element 
        if (top1 < top2 - 1) { 
            top2--; 
            arr[top2] = x; 
        } 
        else { 
            Console.WriteLine("Stack Overflow"); 
            Environment.Exit(1); 
        } 
    } 
  
    // Method to pop an element 
    // from first stack 
    public virtual int pop1() 
    { 
        if (top1 >= 0) { 
            int x = arr[top1]; 
            top1--; 
            return x; 
        } 
        else { 
            Console.WriteLine("Stack Underflow"); 
            Environment.Exit(1); 
        } 
        return 0; 
    } 
  
    // Method to pop an element 
    // from second stack 
    public virtual int pop2() 
    { 
        if (top2 < size) { 
            int x = arr[top2]; 
            top2++; 
            return x; 
        } 
        else { 
            Console.WriteLine("Stack Underflow"); 
            Environment.Exit(1); 
        } 
        return 0; 
    } 
  
    // Driver Code 
    public static void Main(string[] args) 
    { 
        TwoStacks ts = new TwoStacks(5); 
        ts.push1(5); 
        ts.push2(10); 
        ts.push2(15); 
        ts.push1(11); 
        ts.push2(7); 
        Console.WriteLine("Popped element from"
                          + " stack1 is " + ts.pop1()); 
        ts.push2(40); 
        Console.WriteLine("Popped element from"
                          + " stack2 is " + ts.pop2()); 
    } 
} 
  
// This code is contributed by Shrikant13

PHP

<?php 
// PHP program to implement two  
// stacks in a single array      
class twoStacks  
{  
    private $arr;  
    private $size;  
    private $top1; 
    private $top2;  
    function __construct($n) 
    { 
        $this->size = $n;  
        $this->arr = array();  
        $this->top1 = -1;  
        $this->top2 = $this->size;  
    } 
  
// Method to push an element x to stack1  
function push1($x)  
{  
    // There is at least one empty  
    // space for new element  
    if ($this->top1 < $this->top2 - 1)  
    {  
        $this->top1++;  
        $this->arr[$this->top1] = $x;  
    }  
    else
    {  
        echo "Stack Overflow";  
        exit();  
    }  
}  
  
// Method to push an element x to stack2  
function push2($x)  
{  
    // There is at least one empty space 
    // for new element  
    if ($this->top1 < $this->top2 - 1)  
    {  
        $this->top2--;  
        $this->arr[$this->top2] = $x;  
    }  
    else
    {  
        echo "Stack Overflow";  
        exit();  
    }  
}  
  
// Method to pop an element  
// from first stack  
function pop1()  
{  
    if ($this->top1 >= 0 )  
    {  
        $x = $this->arr[$this->top1];  
        $this->top1--;  
        return $x;  
    }  
    else
    {  
        echo "Stack UnderFlow";  
        exit();  
    }  
}  
  
// Method to pop an element from  
// second stack  
function pop2()  
{  
    if ($this->top2 < $this->size)  
    {  
        $x = $this->arr[$this->top2];  
        $this->top2++;  
        return $x;  
    }  
    else
    {  
        echo "Stack UnderFlow";  
        exit();  
    }  
}  
};  
  
  
// Driver Code 
$ts = new twoStacks(5);  
$ts->push1(5);  
$ts->push2(10);  
$ts->push2(15);  
$ts->push1(11);  
$ts->push2(7);  
echo "Popped element from stack1 is " .  
                           $ts->pop1();  
$ts->push2(40);  
echo "\nPopped element from stack2 is " .  
                             $ts->pop2();  
  
// This code is contributed by 
// rathbhupendra 
?>

Javascript

<script> 
// javascript program to implement two stacks in a 
// single array 
class TwoStacks { 
    // Constructor 
    constructor(n) { 
        this.arr = Array(n).fill(0); 
        this.size = n; 
        this.top1 = -1; 
        this.top2 = this.size; 
    } 
   
  
    // Method to push an element x to stack1 
    push1(x) { 
        // There is at least one empty space for 
        // new element 
        if (this.top1 < this.top2 - 1) { 
            this.top1++; 
            this.arr[this.top1] = x; 
        } else { 
            document.write("Stack Overflow"); 
            System.exit(1); 
        } 
    } 
  
    // Method to push an element x to stack2 
     push2(x) { 
        // There is at least one empty space for 
        // new element 
        if (this.top1 < this.top2 - 1) { 
            this.top2--; 
            this.arr[this.top2] = x; 
        } else { 
            document.write("Stack Overflow"); 
            System.exit(1); 
        } 
    } 
  
    // Method to pop an element from first stack 
     pop1() { 
        if (this.top1 >= 0) { 
            var x = this.arr[this.top1]; 
            this.top1--; 
            return x; 
        } else { 
            document.write("Stack Underflow"); 
            System.exit(1); 
        } 
        return 0; 
    } 
  
    // Method to pop an element from second stack 
     pop2() { 
        if (this.top2 < this.size) { 
            var x = this.arr[this.top2]; 
            this.top2++; 
            return x; 
        } else { 
            document.write("Stack Underflow"); 
            System.exit(1); 
        } 
        return 0; 
    } 
  
    // Driver program to test twoStack class 
    } 
        var ts = new TwoStacks(5); 
        ts.push1(5); 
        ts.push2(10); 
        ts.push2(15); 
        ts.push1(11); 
        ts.push2(7); 
        document.write("Popped element from" + " stack1 is " + ts.pop1()); 
        ts.push2(40); 
        document.write("<br/>Popped element from" + " stack2 is " + ts.pop2()); 
  
// This code contributed by Rajput-Ji 
</script>

Output

Popped element from stack1 is 11
Popped element from stack2 is 40

Time Complexity:

Both Push operation: O(1)
Both Pop operation: O(1)

Auxiliary Space: O(N), Use of the array to implement stack.

GeeksforGeeks

Improve

Previous Article

Design and Implement Special Stack Data Structure | Added Space Optimized Version

Implement Stack using Queues

Similar Reads

How to efficiently implement k stacks in a single array?

We have discussed space-efficient implementation of 2 stacks in a single array. In this post, a general solution for k stacks is discussed. Following is the detailed problem statement. Create a data structure kStacks that represents k stacks. Implementation of kStacks should use only one array, i.e., k stacks should use the same array for storing e

Implement Dynamic Multi Stack (K stacks) using only one Data Structure

In this article, we will see how to create a data structure that can handle multiple stacks with growable size. The data structure needs to handle three operations: push(x, stackNum) = pushes value x to the stack numbered stackNumpop(stackNum) = pop the top element from the stack numbered stackNumtop(stackNum) = shows the topmost element of the sta

Merging and Sorting Two Unsorted Stacks

Given 2 input stacks with elements in an unsorted manner. Problem is to merge them into a new final stack, such that the elements become arranged in a sorted manner. Examples: Input : s1 : 9 4 2 1 s2: 8 17 3 10 Output : final stack: 1 2 3 4 8 9 10 17 Input : s1 : 5 7 2 6 4 s2 : 12 9 3 Output : final stack: 2 3 4 5 6 7 9 12 Create an empty stack to

Infix to Prefix conversion using two stacks

Infix: An expression is called the Infix expression if the operator appears in between the operands in the expression. Simply of the form (operand1 operator operand2). Example : (A+B) * (C-D) Prefix: An expression is called the prefix expression if the operator appears in the expression before the operands. Simply of the form (operator operand1 ope

Add two numbers represented by Stacks

Given two numbers N1 and N2 represented by two stacks, such that their most significant digits are present at the bottom of the stack, the task is to calculate and return the sum of the two numbers in the form of a stack. Examples: Input: N1={5, 8, 7, 4}, N2={2, 1, 3} Output: {6, 0, 8, 7}Explanation:Step 1: Popped element from N1(= 4) + Popped elem

Check if two Stacks are equal or not without alteration

Given two Stacks S1 and S2, the task is to check if both the stacks are equal or not in the same order without losing the original stacks. If both the stacks are equal, then print "Yes ". Otherwise, print "No". Examples: Input: S1 = {3, 4, 2, 1}, S2 = {3, 4, 2, 1}Output: Yes Input: S1 = {3, 4, 6}, S2 = {7, 2, 1}Output: No Approach: The given proble

Reversing a Stack using two empty Stacks

Given a stack S, the task is to reverse the stack S using two additional stacks. Example: Input: S={1, 2, 3, 4, 5}Output: 5 4 3 2 1Explanation:The initial stack S:1→top2345After reversing it, use two additional stacks:5→top4321 Input: S={1, 25, 17}Output: 17 25 1 Approach: Follow the steps below to solve the problem: Create two additional empty sta

Check if the two given stacks are same

Given two Stacks, the task is to check if the given stacks are same or not.Two stacks are said to be same if they contains the same elements in the same order.Example: Approach: Take a flag variable and set it to true initially, flag = true. This variable will indicate whether the stacks are same or not.First check if the size of given stack1 and s

Iterative Postorder Traversal | Set 1 (Using Two Stacks)

We have discussed iterative inorder and iterative preorder traversals. In this post, iterative postorder traversal is discussed, which is more complex than the other two traversals (due to its nature of non-tail recursion, there is an extra statement after the final recursive call to itself). Postorder traversal can easily be done using two stacks,

Bubble sort using two Stacks

Prerequisite : Bubble Sort Write a function that sort an array of integers using stacks and also uses bubble sort paradigm. Algorithm: 1. Push all elements of array in 1st stack 2. Run a loop for 'n' times(n is size of array) having the following : 2.a. Keep on pushing elements in the 2nd stack till the top of second stack is smaller than element b

Article Tags :

Practice Tags :