In: Computer Science
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:
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_;
};
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;
};