Programming exercise Remarks: Use linked lists in order to support the following

Question

Programming exercise

Remarks: Use linked lists in order to support the following operations:

1. Push(S, x). Pushes a value x into a stack S

2. Pop(S, i). Gets a number i and pops i numbers of S

3. Reverse(S). Reverse the priority of the elements in S (you might want to apply recursion). If for example S is a stack and x was the last inserted, from now on x is treated as the first inserted element.

4. QUEUE(x, S). Declares that from this moment S becomes and acts like a queue

5. ENQUEUE(S, x). DEQUEUE(S): adds and removes elements when S is a queue.

6. STACK(S). Makes S into a stack

7. Average(S). Returns the average of the numbers in S

For every operation state its running time.

Explanation / Answer

Hi ,

Here is the simple and one program contains all your mentioned exercises

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

using namespace std;

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);
};

bool Stack::isEmpty()
{
if(top == -1)
return true;
return false;
}

bool Stack::isFull()
{
if(top == max - 1)
return true;
return false;
}

int Stack::pop()
{
if(isEmpty())
{
cout<<"Stack Underflow";
abort();
}
int x = arr[top];
top--;
return x;
}

void Stack::push(int x)
{
if(isFull())
{
cout<<"Stack Overflow";
abort();
}
top++;
arr[top] = x;
}

class SpecialStack: public Stack
{
Stack min;
public:
int pop();
void push(int x);
int getMin();
};

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);
}
}

int SpecialStack::pop()
{
int x = Stack::pop();
min.pop();
return x;
}

int SpecialStack::getMin()
{
int x = min.pop();
min.push(x);
return x;
}

int main()
{
SpecialStack s;
s.push(10);
s.push(20);
s.push(30);
cout<<s.getMin()<<endl;
s.push(5);
cout<<s.getMin();
return 0;
}

Output:

10
5

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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