A stack is an Abstract Data Type (ADT) that implements a data structure with las

Question

A stack is an Abstract Data Type (ADT) that implements a data structure

with last-in, first-out (LIFO ) behavior. Common operations on a stack include

push, pop, top, isEmpty, and isFull . This part of your programming assignment

focuses upon building and using a implementation of stacks.

AStack { the implementation of stack will use an array whose bounds are

fixed at creation time. Implementing this program should be trivial now that

you have implemented the Array class.

Your task is to write C++ methods that operate upon objects of class AStack .

Feel free to re-use the class Array you implemented before.

AStack.cpp and main.cpp .

The AStack.h includes class declaration of ADT AStack.

The main.cpp is an empty test driver allows you to test your code.

All you need to do is edit the AStack.cpp to add the methods that implement.

Note:

The pop() and top() methods explicitly check whether the stack is

empty using the is empty() method. The push() method uses the Array::set() method, which grows the array as necessary.

==============================================================================================

Array Class:

Array.h:

#ifndef Array_h
#define Array_h

#include <cstring>

template <typename T>
class Array
{
public:
// === Initialization and termination methods ===

//! Constructor (uninitialized)
// Dynamically create an uninitialized array.
// Throw <std::bad_alloc> if allocation fails
Array (size_t size);

//! Constructor (initialized)
// Dynamically initialize an array.
// Throw <std::bad_alloc> if allocation fails
Array (size_t size, const T& default_value);

//! Copy constructor
// Perform initialization by using another instance.
// Throw <std::bad_alloc> if allocation fails
Array (const Array& s);

//! Assignment operator '='
// Assignment operator performs an assignment by
// making a copy of the contents of parameter <s>
// e.g., *this == s will return true.
// Note that
// if the <max_size> of <array_> is >= than <s.cur_size_>
// we can copy it without reallocating.
// However, if <max_size_> is < than <s.cur_size_>
// we must delete the <array_>
// and reallocate a new Array &operator= (const Array &s);
Array& operator= (const Array& s);

//! Destructor
// Clean up the array (e.g., delete dynamically allocated memory)
~Array (void);

// === Set/get method ===

//! Transformer (Setter)
// Set an item in the array at location index.
// Return -1 if index is larger than the size() of the array,
// else return 0;
int set (const T& new_item, size_t index);

//! Observer (Getter)
// Get an item in the array at location index.
// Return -1 if index is larger than the size() of the array,
// else return 0;
int get (T& item, size_t index) const;

//! Item retrieving operator '[index]'
// Returns a reference to the <index> element in the <Array>
// without checking for range errors.
const T& operator[] (size_t index) const;

//! Item setting operator '[index]'
// Set an item in the array at location index without
// checking for range errors;
T& operator[] (size_t index);

//! Returns the current size of the array
size_t size (void) const;

//! Comparison (equality) operator '=='
// Compare this array with <s> for equality.
// Return true if the size()'s of the two arrays are equal and
// all the elements from 0 ... size() are equal, else false.
bool operator== (const Array& s) const;

//! Comparison (inequality) operator '!='
// Compare this array with <s> for inequality
// such that <*this> != <s> is always the complement of the
// boolean return value of <*this> == <s>.
bool operator!= (const Array& s) const;

private:
//! Within range checking
// Returns true if <index> is within range,
// i.e, 0 <= <index> < <cur_size_>, else return false.
bool in_range (size_t index) const;

//! Maximun size of the array
// i.e., the total number of <T> elements in <array_>.
size_t max_size_;

//! Current size of the array
// This starts out being == to
// <max_size_>. However, if we are assigned a smaller array,
// then <cur_size_> will become less than <max_size_>.
// The purpose of keeping track of both sizes is to avoid
// reallocatiing memory if we don't have to.
size_t cur_size_;

//! Pointer to the array's storage buffer
T* array_;
};

#endif //Array_h

--------------------------------------------------------------------------------------------------------

Array.cpp:

#include "Array.h"
#include <iostream>
#include <exception>
using namespace std;

template <typename T>
Array<T>::Array (size_t size)
{
max_size_=size;
array_=new T[size];
cur_size_=0;

if(array_==NULL){
throw bad_alloc();
}
}

template <typename T>
Array<T>::Array (size_t size, const T& default_value)
{
max_size_=size;
array_=new T[size];
cur_size_=0;

if(array_==NULL){
throw bad_alloc();
}

for(int i=0;i<size;i++){
array_[i]=default_value;
}
cur_size_=size;
}

template <typename T>
Array<T>::Array (const Array<T>& s)
{
max_size_=s.max_size_;
array_=new(nothrow)T[max_size_];
cur_size_=0;

if(!array_){
throw bad_alloc();
}

for(int i=0;i<s.cur_size_;i++){
array_[i]=s.array_[i];
}
cur_size_=s.cur_size_;
}

template <typename T>
Array<T> Array<T>::operator= (const Array<T>& s)
{
if(this!=&s){
delete []array_;
max_size_=s.max_size_;
array_=new T[max_size_];
cur_size_=0;

if(array_=NULL){
throw bad_alloc();
}

for(int i=0;i<s.cur_size_;i++){
array_[i]=s.array_[i];
}
cur_size_=s.cur_size_;
}
return *this;
}

template <typename T>
Array<T>::~Array (void)
{
if(array_!=nullptr){
delete[] array_;
array_=NULL;
}
}

template <typename T>
int Array<T>::set (const T &new_item, size_t index)
{
if(in_range(index)){
array_[index]=new_item;
return 0;
}
else{
return -1;
}
}

template <typename T>
int Array<T>::get (T &item, size_t index) const
{
if(in_range(index)){
item=array_[index];
return 0;
}
else{
return -1
}
}

template <typename T>
const T& Array<T>::operator[] (size_t index) const
{
return array_[index];
}

template <typename T>
T& Array<T>::operator[] (size_t index)
{
return array_[index];
}

template <typename T>
size_t Array<T>::size (void) const
{
return cur_size_;
}

template <typename T>
bool Array<T>::operator== (const Array<T>& s) const
{
if(size()==s.size()){
for(int i=0;i<size();i++){
if(array_[i]!=s.array_[i]){
return false;
}
}
return true;
}
else{
return false;
}
}

template <typename T>
bool Array<T>::operator!= (const Array<T>& s) const
{
return !(*this==s);
}

template <typename T>
bool Array<T>::in_range (size_t index) const
{
if(index>=0&&index<=cur_size_){
return true;
}
else{
return false;
}
}

======================================================================

AStack Class:

AStack.h:

#ifndef AStack_h
#define AStack_h

#include "Array.h"

#include <cstring>

template <typename T>
class AStack
{
public:
// Initialize a new stack so that it is empty.
AStack (size_t size = INITIAL_STACK_SIZE);

// The copy constructor (performs initialization).
AStack (const AStack& s);

// Assignment operator (performs copy assignment).
AStack& operator= (const AStack& s);

// Perform actions needed when stack goes out of scope.
~AStack (void);

// Place a new item on top of the stack.
// Throw the <AStack::overflow()> exception if the stack is full.
void push (const T& new_item);

// Remove and return the top stack item.
// Throws the <AStack::underflow()> exception if the stack is empty.
void pop (T& item);

// Return top stack item without removing it.
// Throws the <AStack::underflow()> exception if the stack is empty.
void top (T& item);

// Returns true if the stack is empty, otherwise returns false.
bool is_empty (void) const;

// Checks for stack equality.
bool operator == (const AStack& s) const;

// Checks for stack inequality.
bool operator != (const AStack& s) const;

// Check if stack is overflow.
bool overflow(void);

// Check if stack is underflow.
bool underflow(void);

private:
// Initial stack size
static const size_t INITIAL_STACK_SIZE = 80;

// Keeps track of the top of the stack.
size_t top_;

// Array that stores the elements in the stack.
Array<T> stack_;
};

#endif /*AStack.h*/

---------------------------------------------------------------------------------------------------------

Stack.cpp:

#include "AStack.h"

template <typename T>
AStack<T> :: AStack (size_t size = INITIAL_STACK_SIZE)
{
/* Your code here */
}

template <typename T>
AStack<T> :: AStack (const AStack<T>& s)
{
/* Your code here */
}

template <typename T>
AStack<T>& AStack<T> :: operator= (const AStack<T>& s)
{
/* Your code here */
}

template <typename T>
AStack<T> :: ~AStack (void)
{
/* Your code here */
}

template <typename T>
void AStack<T> :: push (const T& new_item)
{
/* Your code here */
}

template <typename T>
void AStack<T> :: pop (T& item)
{
/* Your code here */
}

template <typename T>
void AStack<T> :: top (T& item)
{
/* Your code here */
}

template <typename T>
bool AStack<T> :: is_empty (void) const
{
/* Your code here */
}

template <typename T>
bool AStack<T> :: operator == (const AStack<T>& s) const
{
/* Your code here */
}

template <typename T>
bool AStack<T> :: operator != (const AStack& s) const
{
/* Your code here */
}

template <typename T>
bool AStack<T> :: overflow(void)
{
/* Your code here */
}

template <typename T>
bool AStack<T> :: underflow(void)
{
/* Your code here */
}

----------------------------------------------------------------------------------------------

main.cpp:

#include "AStack.h"
#include "AStack.cpp"

#include <iostream>

int main(int argc, char* argv[])
{
  std::cout << " "<<" ";
return 0;
}

Explanation / Answer

here is your Stack.cpp : ----------->>>>>>>>.

#include "AStack.h"
template <typename T>
AStack<T> :: AStack (size_t size = INITIAL_STACK_SIZE)
{
/* Your code here */
stack_ = Array<T>(size);
top_ = -1;
}
template <typename T>
AStack<T> :: AStack (const AStack<T>& s)
{
/* Your code here */
size_t size = s.stack_.size();
stack_ = Array<T>(size);
for(int i = 0;i<size;i++){
  stack_[i] = s.stack_[i];
}
top_ = s.top_;
}
template <typename T>
AStack<T>& AStack<T> :: operator= (const AStack<T>& s)
{
/* Your code here */
size_t size = s.stack_.size();
stack_ = Array<T>(size);
for(int i = 0;i<size;i++){
  stack_[i] = s.stack_[i];
}
top_ = s.top_;

return *this;
}
template <typename T>
AStack<T> :: ~AStack (void)
{
/* Your code here */
//everything is cleaned by the Array class
}
template <typename T>
void AStack<T> :: push (const T& new_item)
{
/* Your code here */
top_++;
if(overflow(void)){
  top_--;
  return;
}
stack_[top_] = new_item;
}
template <typename T>
void AStack<T> :: pop (T& item)
{
/* Your code here */
top_--;
if(underflow()){
  top_ = -1;
}
}
template <typename T>
void AStack<T> :: top (T& item)
{
/* Your code here */
if(is_empty()){
  return;
}
item = stack_[top_];
}
template <typename T>
bool AStack<T> :: is_empty (void) const
{
/* Your code here */
  if(top_ == -1){
   return true;
}

return false;
}
template <typename T>
bool AStack<T> :: operator == (const AStack<T>& s) const
{
/* Your code here */
if(this == &s){
  return true;
}
if(stack_.size() == s.stack_.size()){
  for(int i = 0;i<stack_.size();i++){
   if(stack_[i] != s.stack_[i]){
    return false;
   }
  }
}else{
  return false;
}

return true;
}
template <typename T>
bool AStack<T> :: operator != (const AStack& s) const
{
/* Your code here */
return !(*this == s);
}
template <typename T>
bool AStack<T> :: overflow(void)
{
/* Your code here */
if(top_ >= stack_.size()){
  return true;
}

return false;
}
template <typename T>
bool AStack<T> :: underflow(void)
{
/* Your code here */
if(top_ < -1){
  return true;
}

return false;
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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