Question

In: Computer Science

write an implementation of the ADT stack that uses a resizeable array to represent the stack...

write an implementation of the ADT stack that uses a resizeable array to represent the stack items. Anytime the stack becomes full, double the size of the array. Maintain the stack's top entry at the end of the array. Please use c++ for this question.

Solutions

Expert Solution

#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 getMin() 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::getMin()

{

    int x = min.pop();

    min.push(x);

    return x;

}

  

/* Driver program to test SpecialStack methods */

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 Solutions

Write an implementation of the ADT stack that uses a resizeable array to represent the stack...
Write an implementation of the ADT stack that uses a resizeable array to represent the stack items. Anytime the stack becomes full, double the size of the array. Maintain the stack's top entry at the beginning of the array. Use c++ to write this code.
Write an implementation of the ADT stack that uses a resizeable array to represent the stack...
Write an implementation of the ADT stack that uses a resizeable array to represent the stack items. Anytime the stack becomes full, double the size of the array. Maintain the stack's top entry at the beginning of the array. Use c++ to write this code.
In C++ write an implementation of the ADT sorted list that uses a resizable array (vector...
In C++ write an implementation of the ADT sorted list that uses a resizable array (vector class of C++ STL) to represent the list items.
Question: Write an implementation of the ADT sorted list that uses a resizable array (vector class...
Question: Write an implementation of the ADT sorted list that uses a resizable array (vector class of C++ STL) to represent the list items. Anytime the list becomes full, double the size of the array.
Write an array-based implementation of the ADT list that expands the size of the array of...
Write an array-based implementation of the ADT list that expands the size of the array of list entries as needed so that the list can always accommodate a new entry. Also reduce the size of the array as needed to accommodate several removals. When the size of the array is greater than 20 and the number of entries in the list is less than half the size of the array, reduce the size of the array so that it is...
write a c++ program to perform the following operations on stack of Integers (Array Implementation of...
write a c++ program to perform the following operations on stack of Integers (Array Implementation of Stack with maximum size MAX) (i) Push an Element on to stack (ii) Pop an Element from stack (iii) Demonstrate how stack can be used to check Palindrome (iv) Display the status of stack (v) Exit
Using the Stack ADT: Create a program that uses a stack. Your program should ask the...
Using the Stack ADT: Create a program that uses a stack. Your program should ask the user to input a few lines of text and then outputs strings in reverse order of entry. (Optional) Create a similar program that uses a stack. Your new program should ask the user to input a line of text and then it should print out the line of text in reverse. To do this your application should use a stack of Character. In Java...
2. Using the Stack ADT: Create a program that uses a stack. Your program should ask...
2. Using the Stack ADT: Create a program that uses a stack. Your program should ask the user to input a few lines of text and then outputs strings in reverse order of entry. In Java please.
Write a MIPS program that uses an implementation of quick sort to sort an array of...
Write a MIPS program that uses an implementation of quick sort to sort an array of numbers (Translate the following code into (Mars Assembly language). Quicksort Implementation - C int partition(int arr [] , int left , int right) { int i=left, j=right; int tmp; int pivot = arr[(left + right) / 2]; while (i <= j) { while (arr [ i ] < pivot) i ++; while (arr [ j ] > pivot) j −−; if (i <= j)...
3.1 Implement the stack ADT using array (4 marks) 3.1.1 Implement the pop() operation in the...
3.1 Implement the stack ADT using array 3.1.1 Implement the pop() operation in the stack (1 mark) Implement a stack class named Stack2540Array using array. The starter code is as follows. The instance variables and most operations are provided. You need to implement the pop operation. Make sure that your program checks whether the stack is empty in the pop operation. import java . io .*; import java . util .*; public class Stack2540Array { int CAPACITY = 128; int...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT