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

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...
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...
Develop and test two Java classes: an array-based stack ADT that implements the provided StackInterface.java a...
Develop and test two Java classes: an array-based stack ADT that implements the provided StackInterface.java a linked list-based queue ADT that implements the provided QueueInterface.java You may not make any changes to StackInterface.java or QueueInterface.java The classes must be generic The attached generic singly linked list node class, LLNode.java, must be used for the queue implementation; you may not make any modifications to this class Your implementations cannot throw any exceptions Each ADT must include a toString( ) method: The...
Complete the implementation of the Die class. Note that the Die class uses an array to...
Complete the implementation of the Die class. Note that the Die class uses an array to represent the faces of a die. You need to complete the no-argument constructor and the two methods compareTo and equals. Code: import java.util.Arrays; import java.util.Objects; import java.util.Random; /* * NOTE TO STUDENTS: * The constructor that you need to complete can be found on line 47. * * The two methods you need to complete can be found at the end of this file....
Using the implementation of the array based list given, write a CLIENT method (that is NOT...
Using the implementation of the array based list given, write a CLIENT method (that is NOT part of the class) called replace, that given a value and a position replaces the value of the element at that position. REMEMBER error checking public static void replace( List aList, int newValue, int position) public class ArraybasedList implements MyListInterface{ private static final int DEFAULTSIZE = 25; // Data members: private int currentSize; private int maxSize; private S[] elements; //default constructor has NO parameters...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT