1.
Introduction
2.
Problem Statement
3.
Example
4.
Algorithm Used
5.
Implementation in C++
6.
Implementation in Java
7.
Time Complexity
8.
Space Complexity
9.
9.1.
Why is Stack used in data structure?
9.2.
Stack is what kind of data structure?
9.3.
What are the principal operations of a Stack?
9.4.
What is the meaning of overflow and Underflow in Stack?
9.5.
In how many ways can Stack be implemented?
10.
Conclusion
Last Updated: Mar 27, 2024
Medium

Special Stack Data Structure Design and Implementation

Introduction

In this special stack data structure problem, we have to add only one additional operation, getMin(), that returns the minimum element from the stack.

We all know that the stack contains various operations such as push(), pop(), top(), isempty(). In addition, we have to create a getMin() function to solve the special stack data structure problem.

In this article, we will discuss the special stack Data Structure problem with their implementation both in C++ and Java.

Problem Statement

The problem statement of special stack data structure design and implementation is that we have to design a data structure SpecialStack that supports all the Stack operations like push(), pop(), isempty(), isfull(), and a getMin() operation that returns the minimum element from the Stack. We have to do this operation in O(1) time. Also, to implement SpecialStack, we have to use only a standard stack data structure.

Let's see the example to understand the special stack data structure problem.

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.

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.

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