Special Stack Data Structure Design and Implementation

Example

Let us see some examples to understand the problem statement better.

Stack:

12 6 8 16 10

 

When getMin() is called -

6 (minimum element from the Stack).

 

pop() 

Stack becomes: 

6 8 16 10

 

push(2)

Stack becomes: 

2 6 8 16 10

 

When getMin() is called - 

2 (minimum element from the Stack).

 

Let us see the approach to solving the special stack data structure problem.

Algorithm Used

We will use two stacks, one is to store actual stack elements, and the other is used as an auxiliary stack.

• Push( int x) - Insert elements to the stack. 

    Push x to the actual Stack.

    top1= top of the actual Stack.

    top2= top of the auxiliary Stack.

    If top1<top2 - Push top1 to the auxiliary Stack.

    If top1>top2 - Push top2 to the auxiliary Stack.

• int pop() - Remove the element from the stack

    1. Pop the top element of the auxiliary Stack.

    2. Pop the top element of the actual Stack.

• int getMin() - Return minimum element from the stack.

    Returns top element from the auxiliary Stack.

Below is the implementation of the above algorithm in both C++ and Java.

Implementation in C++

Let us learn the implementation of the above algorithm in C++.

#include <iostream>
#include <stdlib.h>  
using namespace std;
  
//Stack class with basic functionalties
class stack {
private:
    static const int max = 100;
    int arr[max];
    int top;
  
public:
    stack() { top = -1; }
    bool isEmpty();
    bool isFull();
    int pop();
    void push(int a);
};
  
//Function to check if stack is empty or not
bool stack::isEmpty()
{
    if (top == -1)
        return true;
    return false;
}
  
//Functin to check if stack is full or not
bool stack::isFull()
{
    if (top == max - 1)
        return true;
    return false;
}
  
//Function to remove an element from it
int stack::pop()
{
    if (isEmpty()) {
        cout << "Stack Underflow";
        abort();
    }
    int a = arr[top];
    top--;
    return a;
}
  
//Function to insert an element to it
void stack::push(int a)
{
    if (isFull()) {
        cout << "Stack Overflow";
        abort();
    }
    top++;
    arr[top] = a;
}
  
// A class that supports all the stack operations and one additional operation getMin() that returns the minimum element from stack at any time.
class specialStack : public stack {
    stack min;
  
public:
    int pop();
    void push(int a);
    int getMin();
};
  
// SpecialStack's member method to insert an element to it.
void specialStack::push(int a)
{
    if (isEmpty() == true) {
        stack::push(a);
        min.push(a);
    }
    else {
        stack::push(a);
        int b = min.pop();
        min.push(b);
        if (a < b)
            min.push(a);
        else
            min.push(b);
    }
}
  
//Function to remove an element from it.
int specialStack::pop()
{
    int a = stack::pop();
    min.pop();
    return a;
}
  
//Function to get minimum element from it.
int specialStack::getMin()
{
    int a = min.pop();
    min.push(a);
    return a;
}
  
//Driver program
int main() 
{ 
    specialStack s; 
    s.push(5); 
    s.push(10); 
    s.push(15);
    s.push(20);
    cout<<s.getMin()<<endl; 
    s.push(1); 
    cout<<s.getMin(); 
    return 0; 
} 

The above program handles both Overflow and Underflow conditions.

Must Read Stack Operations

Implementation in Java

Let us learn the implementation of the above algorithm in Java.

import java.util.Stack;  
class SpecialStack extends Stack<Integer> {
    Stack<Integer> min = new Stack<>();
    void push(int x)
    {
        if (isEmpty() == true) {
            super.push(x);
            min.push(x);
        }
        else {
            super.push(x);
            int y = min.pop();
            min.push(y);
            if (x < y)
                min.push(x);
            else
                min.push(y);
        }
    }
 
    public Integer pop()
    {
        int x = super.pop();
        min.pop();
        return x;
    }
 
    int getMin()
    {
        int x = min.pop();
        min.push(x);
        return x;
    }
    
    public static void main(String[] args)
    {
        SpecialStack s = new SpecialStack();
        s.push(5);
        s.push(10);
        s.push(15);
        s.push(20);
        System.out.println(s.getMin());
        s.push(1);
        System.out.println(s.getMin());
    }
}

 

Input Stack: 

5 10 15 20

Output: 

5

As 5 is the minimum element of the given stack. So, the output is 5.

Input Stack: 

5 10 15 20 1

Output: 

1

 

Here, the output is 1 because after the push operation stack contains 1 as the minimum element.

Time Complexity

The time complexity of this algorithm is O(1) as,

• Insertion (Push) - It requires constant time.
• Deletion (Pop) - It requires constant time.
• getmin() - It also requires constant time complexity.

Space Complexity

The space complexity of this algorithm is O(N), as we have used an auxiliary stack for storing elements.

We have already seen the algorithm and implementation of a special stack data structure. Now let's see some FAQs.

Must Read Difference between ArrayList and LinkedList, hash function in data structure

Frequently Asked Questions

Why is Stack used in data structure?

Stack is used in data structure because of its LIFO (Lst In First Out) principle. It enables data to operate at one end only.

Stack is what kind of data structure?

Stack is a linear data structure in which the elements are arranged in sequential order, i.e., one after the other.

What are the principal operations of a Stack?

Push and Pop are a stack's principal operations that add an element to the Stack and remove an element from the Stack, respectively.

What is the meaning of overflow and Underflow in Stack?

Overflow happens when we want to add some element to the Stack when the Stack is full, and Underflow occurs when we want to remove some element from the Stack when the Stack is empty.

In how many ways can Stack be implemented?

The Stack can be implemented in two ways-

• Array
• Linked List

Conclusion

We had designed a data structure, SpecialStack, which contains an additional operation getMin() which gives a minimum element from the Stack. We have used stack operations in O(1).

After reading about the famous problem "Special Stack Data Structure Design and Implementation," are you not feeling excited to read/explore more articles on Data Structures and Algorithms? Don't worry; Coding Ninjas has you covered. See Implement stack using a singly linked list, Next Greater Element, Delete Middle Element Of The Stack,  Print Stack Elements from Top to Bottom, and Reverse an array using Stack to learn.

You can also consider our Mern Stack Course to give your career an edge over others.

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!