For problems where either pseudo-code or C++ code is required, you may simply in

Question

For problems where either pseudo-code or C++ code is required, you may simply include the algorithm written as pseudo-code without being tested as long as the logic is clear and can be easily understood by the grader

Consider an ordinary stack of integers that implements the usual push() and pop() operations in constant time. Describe an algorithm that implements an auxiliary stack alongside the ordinary stack such that the push() and pop() operations occur in constant time, but also keep track of the element currently in the ordinary stack with the minimum value in constant time. That is, design the auxiliary stack with these operations such that a user can push(), pop(), and findMin() any number of times and still perform these operations in constant time

Explanation / Answer

Please find my answer.

We can use two stacks:

1.one to store actual stack elements and

2 .other as an auxiliary stack to store minimum values.

The idea is to do push() and pop() operations in such a way that the top of auxiliary stack is always the minimum.

Let us see how push() and pop() operations work.

Push(int x) // inserts an element x to Special Stack
1) push x to the first stack (the stack with actual elements)
2) compare x with the top element of the second stack (the auxiliary stack). Let the top element be y.
…..a) If x is smaller than y then push x to the auxiliary stack.
…..b) If x is greater than y then push y to the auxiliary stack.

int Pop() // removes an element from Special Stack and return the removed element
1) pop the top element from the auxiliary stack.
2) pop the top element from the actual stack and return it.

The step 1 is necessary to make sure that the auxiliary stack is also updated for future operations.

int findMin() // returns the minimum element from Special Stack
1) Return the top element of auxiliary stack.

We can see that all above operations are O(1).

Let us see an example. Let us assume that both stacks are initially empty and 18, 19, 29, 15 and 16 are inserted to the SpecialStack.

When we insert 18, both stacks change to following.
Actual Stack
18 <--- top   
Auxiliary Stack
18 <---- top

When 19 is inserted, both stacks change to following.
Actual Stack
19 <--- top   
18
Auxiliary Stack
18 <---- top
18

When 29 is inserted, both stacks change to following.
Actual Stack
29 <--- top   
19
18
Auxiliary Stack
18 <---- top
18
18

When 15 is inserted, both stacks change to following.
Actual Stack
15 <--- top   
29
19
18
Auxiliary Stack
15 <---- top
18
18
18

When 16 is inserted, both stacks change to following.
Actual Stack
16 <--- top   
15
29
19
18
Auxiliary Stack
15 <---- top
15
18
18
18

C++ Code:

#include<iostream>
#include<stdlib.h>

using namespace std;

/* A simple stack class with basic stack funtionalities */
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 x);
};

/* Stack's member method to check if the stack is iempty */
bool Stack::isEmpty()
{
if(top == -1)
return true;
return false;
}

/* Stack's member method to check if the stack is full */
bool Stack::isFull()
{
if(top == max - 1)
return true;
return false;
}

/* Stack's member method to remove an element from it */
int Stack::pop()
{
if(isEmpty())
{
cout<<"Stack Underflow";
abort();
}
int x = arr[top];
top--;
return x;
}

/* Stack's member method to insert an element to it */
void Stack::push(int x)
{
if(isFull())
{
cout<<"Stack Overflow";
abort();
}
top++;
arr[top] = x;
}

/* A class that supports all the stack operations and one additional
operation findMin() that returns the minimum element from stack at
any time. This class inherits from the stack class and uses an
auxiliarry stack that holds minimum elements */
class SpecialStack: public Stack
{
Stack min;
public:
int pop();
void push(int x);
int getMin();
};

/* SpecialStack's member method to insert an element to it. This method
makes sure that the min stack is also updated with appropriate minimum
values */
void SpecialStack::push(int x)
{
if(isEmpty()==true)
{
Stack::push(x);
min.push(x);
}
else
{
Stack::push(x);
int y = min.pop();
min.push(y);
if( x < y )
min.push(x);
else
min.push(y);
}
}

/* SpecialStack's member method to remove an element from it. This method
removes top element from min stack also. */
int SpecialStack::pop()
{
int x = Stack::pop();
min.pop();
return x;
}

/* SpecialStack's member method to get minimum element from it. */
int SpecialStack::findMin()
{
int x = min.pop();
min.push(x);
return x;
}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.