Question

In: Computer Science

Write a C++ class that implement two stacks using a single C++ array. That is, it...

Write a C++ class that implement two stacks using a single C++ array. That is, it should have functions pop_first(), pop_second(), push_first(…), push_second(…), size_first(), size_second(), …. When out of space, double the size of the array (similarly to what vector is doing).

Notes:

  • Complete all the functions in exercise_2.cpp, then submit this cpp file.
  • pop_first() and pop_second() should throw std::out_of_range exception when stack is empty.

CODE:

#include <cstdio>

#include <stdexcept>

template <class T>

class TwoStacks {

public:

  // Constructor, initialize the array to size_hint

  TwoStacks(size_t size_hint = 16) : size_(size_hint), array_(new T(size_hint)) {}

  // Destructor

  ~TwoStacks() { delete array_; }

  // Push a value to the first stack

  void push_first(const T& val) {

    // Implement here

    

  }

  // Push a value to the second stack

  void push_second(const T& val) {

    // Implement here

  }

  // Pop from the first stack and return the value

  T pop_first() {

    // Implement here, throw std::out_of_range if necessary

  }

  // Pop from the second stack and return the value

  T pop_second() {

    // Implement here, throw std::out_of_range if necessary

  }

  // Return the size of the first stack

  size_t size_first() const {

    // Implement here

  }

  // Return the size of the second stack

  size_t size_second() const {

    // Implement here

  }

  // Return true if the first stack is empty

  bool empty_first() const { return size_first() == 0; }

  // Return true if the second stack is empty

  bool empty_second() const { return size_second() == 0; }

private:

  size_t size_;

  T *array_;

};

Solutions

Expert Solution

CODE:

#include <cstdio>

#include <stdexcept>

template <class T>

class TwoStacks {

public:

   // Constructor, initialize the array to size_hint

   TwoStacks(size_t size_hint = 16) : size_(size_hint), array_(new T(size_hint)) {}

   // Destructor

   ~TwoStacks() { delete array_; }

   // Push a value to the first stack

   void push_first(const T& val) {

       if(current_size_ >= size_)
       {
           array_ = (T*)realloc(array_, size_ * 2);
           size_ *= 2;
       }
      
       array_[current_size_++] = val;

   }

   // Push a value to the second stack

   void push_second(const T& val) {

       if (current_size_ >= size_)
       {
           array_ = (T*)realloc(array_, size_ * 2);
           size_ *= 2;
       }

       array_[current_size_++] = val;

   }

   // Pop from the first stack and return the value

   T pop_first() {

       // Implement here, throw std::out_of_range if necessary
       if (current_size_ == 0)
           throw std::out_of_range("Out of range exception");
      
       T temp = array_[current_size_ - 1];

       --current_size_;
      
       return temp;
   }

   // Pop from the second stack and return the value

   T pop_second() {

       if (current_size_ == 0)
           throw std::out_of_range("Out of range exception");

       T temp = array_[current_size_ - 1];

       --current_size_;

       return temp;

   }

   // Return the size of the first stack

   size_t size_first() const {

       return current_size_;

   }

   // Return the size of the second stack

   size_t size_second() const {

       return current_size_;

   }

   // Return true if the first stack is empty

   bool empty_first() const { return size_first() == 0; }

   // Return true if the second stack is empty

   bool empty_second() const { return size_second() == 0; }

private:

   size_t size_;

   T* array_;

   size_t current_size_ = 0;

};


Related Solutions

1. You are given Stack.java, an interface class for Stacks. /* Use an array to implement...
1. You are given Stack.java, an interface class for Stacks. /* Use an array to implement the Stack.java in a class called ArrayStack.java that uses Generics. Write a main function that creates two stacks, one containing 10 Integers and a different one containing 10 Strings, and reverses there contents using a method called reverse that takes as a paramater a Generic array. You will need to implement all the methods of Stack.java as well as create a toString method in...
Implement a Binary tree using an array using class.
Implement a Binary tree using an array using class.
C++ Write the code to implement a complete binary heap using an array ( Not a...
C++ Write the code to implement a complete binary heap using an array ( Not a vector ). Code for Max heap. Implement: AddElement, GetMax, HeapSort, ShuffleUp, ShuffleDown, etc Set array size to 31 possible integers. Add 15 elements 1,3,27,22,18,4,11,26,42,19,6,2,15,16,13 Have a default constructor that initializes the array to zeros.. The data in the heap will be double datatype. PART 2 Convert to the program to a template, test with integers, double and char please provide screenshots thank you so...
Show how to implement three stacks in one array (in Java)
Show how to implement three stacks in one array (in Java)
We are trying to use two stacks to implement a queue. Name the two stacks as...
We are trying to use two stacks to implement a queue. Name the two stacks as E and D. We will enqueue into E and dequeue from D. To implement enqueue(e), simply call E.push(e). To implement dequeue(), simply call D.pop(), provided that D is not empty. If D is empty, iteratively pop every element from E and push it onto D, until E is empty, and then call D.pop(). Considering the worst case running time, what is the performance in...
Implement a class named stack pair that provides a pair of stacks. Make the class a...
Implement a class named stack pair that provides a pair of stacks. Make the class a template class. So, you will have two files: stack pair.h and stack pair.template, following the style of the text. The basic idea is that two stacks can share a single static array. This may be advantageous if only one of the stacks will be in heavy use at any one time. • The class should have various methods to manipulate the stack: T pop...
in C++ For this program, you are going to implement a stack using an array and...
in C++ For this program, you are going to implement a stack using an array and dynamic memory allocation. A stack is a special type of data structure that takes in values (in our case integers) one at a time and processes them in a special order. Specifically, a stack is what's called a first-in-last-out (FILO) data structure. That is to say, the first integer inserted into the stack is the last value to be processed. The last value in...
you are asked to implement a C++ class to model a sorted array of unsigned integers....
you are asked to implement a C++ class to model a sorted array of unsigned integers. The class is to be used in an embedded application that cannot assume the presence of the STL. The array has to be dynamically allocated in such a way that allows programmers using it to specify the required size. Class will provide (1) provide the appropriate constructors and destructor; (2) provide methods for updating, and showing numbers in/to the array (e.g., to be used...
           Homework: Polynomial Using Array Description: Implement a polynomial class (1) Name your class...
           Homework: Polynomial Using Array Description: Implement a polynomial class (1) Name your class Polynomial (2) Use array of doubles to store the coefficients so that the coefficient for x^k is stored in the location [k] of the array. (3) define the following methods: a. public Polynomial()    POSTCONDITION: Creates a polynomial represents 0 b. public Polynomial(double a0)    POSTCONDITION: Creates a polynomial has a single x^0 term with coefficient a0 c. public Polynomial(Polynomial p)    POSTCONDITION: Creates...
Write a class VectorInt to implement the concept of one dimensional array of integers with extendable...
Write a class VectorInt to implement the concept of one dimensional array of integers with extendable array size. Your class should support storing an integer at a specific index value, retrieving the integer at a specific index value, and automatically increasing storage for the saved values.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT