Growable array based stack

Difficulty Level Medium
Frequently asked in MAQ Walmart Labs
Array StackViews 2011

Problem Statement

Growable array-based stack is used in cases of “stack full”. Here the old array is replaced with the new bigger one. The size of the new array is decided using these two strategies-

  • Tight Strategy – In this case, a constant amount say c is added to the already existing stack i.e. n = n+c where n is the size of the existing stack.
  • Growth Strategy – In this case, we double the size of the existing stack i.e. n = 2n.

Write a program to implement growable array-based stack.

Growable array based stack

Example

push(100)

push(200)

push(300)

display()

push(400)

display()
Stack: 100 200 300

Stack: 100 200 300 400

Explanation: We have performed the basic operations of a stack. So, first, we pushed 100, 200, 300, and then displayed the stack content. After we pushed 400 and after that, we again displayed the stack content.

push(1)

push(2)

display()

push(3)

display()
Stack: 1 2

Stack: 1 2 3

Algorithm for Growable array based stack

1. Create three global variables bound, top, and length, and initialize them as 3, -1, and 0 respectively.
2. After that, create a function to create extra space for an array-based stack that accepts an integer array as it's parameter.
3. Initialize a new array inside the function of length equals the sum of the length of given array and the bound variable.
4. Traverse through the given array and update the value at the current index in the new array as the value at the current index in the given array.
5. Update the variable-length as the sum of variable length itself and the bound variable and return the new array.
6. Similarly, create a function to push/insert the elements which accept an integer array and an integer variable as it's parameter.
7. Check if the value of top is equal to the length - 1, call the function to create a new array. Store the integer variable in the array at index equals to top + 1 and return the array.
8. After that, create a function to pop/remove the top element from the array. Decrement the variable top by 1.
9. Similarly, create a function to print the elements in the array which accepts an integer array as it's a parameter.
10. Check if the top is equal to -1, print "Stack is Empty".
11. Else print the array.

Here we have used tight strategy, where whenever we need to increase the size of the stack. We simply keep on adding the same BOUND every time. So, whenever we need to add an extra size to the array, we need to copy the original array into the new array and then we add the new element. This approach is good if we are bound with less space. But if we want better time complexity we should go with growth strategy.

Code

C++ Program for growable array-based stack

#include <iostream> 
using namespace std; 
  
#define BOUND 3
  
int top = -1; 
  
int length = 0; 
  
int* create_new(int* a){ 
    int* new_a = new int[length + BOUND]; 
  
    for(int i = 0; i < length; i++){ 
        new_a[i] = a[i]; 
    }
  
    length += BOUND; 
    return new_a; 
} 
  
int* push(int* a, int element){ 
    if(top == length - 1){ 
        a = create_new(a);
    }
  
    a[++top] = element; 
    return a; 
} 
  
void pop(int* a){ 
    top--; 
} 
  
void display(int* a){ 
    if(top == -1){ 
        cout << "Stack is Empty" << endl; 
    }
    
    else{ 
        cout << "Stack: "; 
        for(int i = 0; i <= top; i++){ 
            cout << a[i] << " "; 
        }
        cout << endl; 
    } 
} 
  
int main(){ 
    int *a = create_new(a); 
  
    a = push(a, 100); 
    a = push(a, 200); 
    a = push(a, 300); 
    display(a); 
    a = push(a, 400); 
    display(a); 
  
    return 0; 
}
Stack: 100 200 300 
Stack: 100 200 300 400

Java Program for growable array-based stack

class GrowableStack{ 
  
    static final int BOUND = 3; 
      
    static int top = -1; 
      
    static int length = 0; 
      
    static int[] create_new(int[] a){ 
        int[] new_a = new int[length + BOUND]; 
      
        for(int i = 0; i < length; i++){ 
            new_a[i] = a[i]; 
        }
      
        length += BOUND; 
        return new_a; 
    } 
      
    static int[] push(int[] a, int element){ 
        if(top == length - 1){ 
            a = create_new(a);
        }
      
        a[++top] = element; 
        return a; 
    } 
      
    static void pop(int[] a){ 
        top--; 
    } 
      
    static void display(int[] a){ 
        if(top == -1){ 
            System.out.println("Stack is Empty");
        }
        
        else{ 
            System.out.print("Stack: "); 
            for(int i = 0; i <= top; i++){ 
                System.out.print(a[i] + " ");
            }
            System.out.println(); 
        } 
    } 
      
    public static void main(String args[]){ 
        int []a = create_new(new int[length + BOUND]); 
      
        a = push(a, 100); 
        a = push(a, 200); 
        a = push(a, 300); 
        display(a); 
      
        a = push(a, 400); 
        display(a); 
    } 
}
Stack: 100 200 300 
Stack: 100 200 300 400

Complexity Analysis

Time Complexity

O(N), because we have are simply pushing the elements into the stack. Here N is the number of elements being pushed. Since all of these operations are O(1) that is constant-time operations. So, doing these operations for N time will result into linear time complexity algorithm.

Space Complexity

O(N), where N is the number of elements in the stack. Because we have used a single stack that is storing N elements. Thus the algorithm has linear space complexity.

Translate ยป