This program is an exercise in implementing the stack ADT using an array-based d
ID: 3675275 • Letter: T
Question
This program is an exercise in implementing the stack ADT using an array-based data structure.
This program needs stack.cpp. You can't modify main.cpp or stack.h. I've provided the input files and what the outputs should look like.
Push operation should invoke the Resize() function which attempts to double the capacity of the stack and then add the new data value to the resized stack array. In Resize() a new array (that holds twice as many integers) is dynamically allocated, data from the old stack array is copied into the new larger stack array, the old stack array is deallocated, and the new data value is pushed onto the new array.
// main.cpp
#include <iostream>
#include <fstream>
#include <new>
#include <cstddef>
#include "stack.h"
using namespace std;
int main(int argc, char* argv[])
{
ifstream inputs; // Input file for commands
char op; // Hold operation and optional char input
int value; // Value input from file
string comment; // Holds comment from file
Stack* sPtr = NULL; // Will point to TemplateQ object
// Output usage message if one input file name is not provided
if (argc != 2)
{
cout << "Usage: project03 <inputfile> ";
return 1;
}
// Attempt to open input file -- terminate if file does not open
inputs.open(argv[1]);
if (!inputs)
{
cout << "Error - unable to open input file" << endl;
return 1;
}
// Input and echo header comment from file
getline(inputs, comment); // Input and echo the comment appearing in the test file
cout << endl << '#' << comment << endl;
// Process commands from input file
inputs >> op; // Attempt to input first command
while (inputs)
{
switch (op) // Process operation input from file
{
case '#': // Test file comment
getline(inputs, comment); // Input and echo the comment appearing in the test file
cout << '#' << comment << endl;
break;
case 'c': // Parameterized Constructor
inputs >> value;
cout << endl << "Stack(" << value << ")";
try
{
sPtr = new Stack(value); // Attempt to create a stack object with array size value
cout << " -- completed" << endl;
}
catch ( std::bad_alloc )
{
cout << "Failed : Terminating now..." << endl;
return 1;
}
break;
case '+': // Push
inputs >> value;
cout << "Push(" << value << ") -- ";
try
{
sPtr->Push(value);
cout << "completed";
}
catch (StackFull)
{
cout << "Failed Full Stack";
}
catch (...)
{
cout << "operation failed" << endl;
}
cout << endl;
break;
case '-': // Pop
cout << "Pop() -- ";
try
{
sPtr->Pop();
cout << "completed";
}
catch (StackEmpty)
{
cout << "Failed Empty Stack";
}
catch (...)
{
cout << "operation failed" << endl;
}
cout << endl;
break;
case 'f': // IsFull
cout << "IsFull() -- ";
try
{
if (sPtr->IsFull())
cout << "true";
else
cout << "false";
}
catch ( ... )
{
cout << "operation failed";
}
cout << endl;
break;
case 'e': // IsEmpty
cout << "IsEmpty() -- ";
try
{
if (sPtr->IsEmpty())
cout << "true";
else
cout << "false";
}
catch ( ... )
{
cout << "operation failed";
}
cout << endl;
break;
case 'm': // Make Empty
cout << "MakeEmpty() -- ";
try
{
sPtr->MakeEmpty();
cout << "completed" << endl;
}
catch (...)
{
cout << "operation failed" << endl;
}
break;
case 'p': // Print Stack
cout << "Print() -- ";
sPtr->Print();
break;
case 't': // Top of Stack
try
{
cout << "Top() -- " << sPtr->Top() << endl;
}
catch (StackEmpty)
{
cout << "Top() -- Failed Empty Stack" << endl;
}
catch (...)
{
cout << "operation failed" << endl;
}
break;
case '>': // Max value within Stack
try
{
cout << "Max() -- " << sPtr->Max() << endl;
}
catch (StackEmpty)
{
cout << "Max() -- Failed Empty Stack" << endl;
}
catch (...)
{
cout << "operation failed" << endl;
}
break;
case '<': // Min value within Stack
try
{
cout << "Min() -- " << sPtr->Min() << endl;
}
catch (StackEmpty)
{
cout << "Min() -- Failed Empty Stack" << endl;
}
catch (...)
{
cout << "operation failed" << endl;
}
break;
case '?': // Peek(n) Stack
inputs >> value;
try
{
cout << "Peek(" << value << ") -- " << sPtr->Peek(value) << endl;
}
catch (StackInvalidPeek)
{
cout << "Peek(" << value << ") -- Failed Invalid Peek" << endl;
}
catch (...)
{
cout << "operation failed" << endl;
}
break;
case 's': // Size of Stack
cout << "Size() -- ";
try
{
cout << sPtr->Size() << endl;
}
catch (...)
{
cout << "operation failed" << endl;
}
break;
case 'z': // Capacity of Stack
cout << "Capacity() -- ";
try
{
cout << sPtr->Capacity() << endl;
}
catch (...)
{
cout << "operation failed" << endl;
}
break;
case 'd': // Destructor
cout << "~Stack() -- ";
try
{
delete sPtr;
sPtr = NULL;
cout << "completed" << endl << endl;
}
catch (...)
{
cout << "operation failed" << endl << endl;
}
break;
default: // Error
cout << "Error - unrecognized operation '" << op << "'" << endl;
cout << "Terminating now..." << endl;
return 1;
break;
}
inputs >> op; // Attempt to input next command
}
return 0;
} // End main()
// stack.h
#include <iostream>
using namespace std;
#ifndef STACK_H
#define STACK_H
class StackEmpty
{
// Exception class - throw an object of this type when stack is empty
// Hint: there is no code for exception classes
};
class StackFull
{
// Exception class - throw an object of this type when stack is full
};
class StackInvalidPeek
{
// Exception class - throw an object of this type when invalid peek position is used
};
class Stack // Models stack of integers ADT implemented as a dynamically allocated array
{
private:
int* array; // Points to the stack array
int num; // Holds max number of elements that may be stored in stack array
int top; // Holds the index of the top data value stored on the stack
void Resize(int n); // Attempts to increase size of stack array to 2*num and then push n onto stack
// If unable to resize, throw StackFull exception
public:
Stack(int n); // Parameterized constructor dynamically allocates an empty stack array
// that may hold no more than n elements and initializes other private variables
~Stack(); // Destructor deallocates all dynamically-allocated memory
// associated with the object
void Push(int n); // Pushes integer n onto top of stack. If stack is full, attempts to
// resize stack and then push n. If unable to resize, throws StackFull exception.
void Pop(); // Removes top integer from stack
// If stack is empty, throws StackEmpty exception
bool IsEmpty() const; // Returns true if stack is empty; false otherwise
bool IsFull() const; // Returns true if stack is full; false otherwise
void MakeEmpty(); // Removes all items from stack leaving an empty, but usable stack with capacity num
// If stack is already empty, MakeEmpty() does nothing
int Top() const; // Returns value of top integer on stack WITHOUT modifying the stack
// If stack is empty, throws StackEmpty exception
int Size() const; // Returns number of items on stack WITHOUT modifying the stack
int Max() const; // Returns value of largest integer on stack WITHOUT modifying the stack
// If stack is empty, throws StackEmpty
int Min() const; // Returns value of smallest integer on stack WITHOUT modifying the stack
// If stack is empty, throws StackEmpty
int Peek(unsigned int n) const; // Returns stack value n levels down from top of stack. Peek(0) = Top()
// If position n does not exist, throws StackInvalidPeek
int Capacity() const; // Returns total num of elements that maybe stored in stack array
void Print() const // Writes stack contents to stdout, separated by a space, followed by endl
{
int index = top;
cout << "Top { ";
while (index != -1)
{
cout << array[index] << " ";
index--;
}
cout << "} Bottom" << endl;
} // End Print()
}; // End Class Stack
#endif
// input 1
# input1.txt -- Test: Stack(), Push(), Pop(), Top(), ~Stack()
# Test: Stack(), Push(), Pop(), Top(), ~Stack()
c 8
p
t
+ 5
+ 10
+ 15
p
t
+ 20
+ 25
+ 30
p
t
-
-
p
+ 35
+ 40
t
+ 45
t
p
-
-
-
-
-
-
-
-
p
t
d
# Test: Stack(), Push(), Pop(), Top(), ~Stack()
c 4
p
-
t
d
// output 1
## input1.txt -- Test: Stack(), Push(), Pop(), Top(), ~Stack()
# Test: Stack(), Push(), Pop(), Top(), ~Stack()
Stack(8) -- completed
Print() -- Top { } Bottom
Top() -- Failed Empty Stack
Push(5) -- completed
Push(10) -- completed
Push(15) -- completed
Print() -- Top { 15 10 5 } Bottom
Top() -- 15
Push(20) -- completed
Push(25) -- completed
Push(30) -- completed
Print() -- Top { 30 25 20 15 10 5 } Bottom
Top() -- 30
Pop() -- completed
Pop() -- completed
Print() -- Top { 20 15 10 5 } Bottom
Push(35) -- completed
Push(40) -- completed
Top() -- 40
Push(45) -- completed
Top() -- 45
Print() -- Top { 45 40 35 20 15 10 5 } Bottom
Pop() -- completed
Pop() -- completed
Pop() -- completed
Pop() -- completed
Pop() -- completed
Pop() -- completed
Pop() -- completed
Pop() -- Failed Empty Stack
Print() -- Top { } Bottom
Top() -- Failed Empty Stack
~Stack() -- completed
# Test: Stack(), Push(), Pop(), Top(), ~Stack()
Stack(4) -- completed
Print() -- Top { } Bottom
Pop() -- Failed Empty Stack
Top() -- Failed Empty Stack
~Stack() -- completed
// input 2
# input2.txt -- Test IsFull(), IsEmpty(), MakeEmpty()
# Size(), Capacity()
# Test IsFull(), IsEmpty(), MakeEmpty()
c 8
e
f
+ 5
+ 10
+ 15
+ 20
+ 25
+ 30
p
e
f
m
p
e
f
+ 35
+ 40
+ 45
+ 50
p
e
f
-
-
-
p
e
f
m
p
e
f
d
# Test Size()
c 6
p
s
+ 5
+ 10
p
s
+ 15
+ 20
p
s
+ 25
+ 30
p
s
-
-
-
p
s
-
-
-
p
s
d
# Test Capacity()
c 2
z
+ 5
z
+ 10
z
+ 15
z
+ 20
z
+ 25
z
+ 30
z
p
-
-
-
z
p
-
-
-
z
p
d
// output 2
## input2.txt -- Test IsFull(), IsEmpty(), MakeEmpty()
# Size(), Capacity()
# Test IsFull(), IsEmpty(), MakeEmpty()
Stack(8) -- completed
IsEmpty() -- true
IsFull() -- false
Push(5) -- completed
Push(10) -- completed
Push(15) -- completed
Push(20) -- completed
Push(25) -- completed
Push(30) -- completed
Print() -- Top { 30 25 20 15 10 5 } Bottom
IsEmpty() -- false
IsFull() -- false
MakeEmpty() -- completed
Print() -- Top { } Bottom
IsEmpty() -- true
IsFull() -- false
Push(35) -- completed
Push(40) -- completed
Push(45) -- completed
Push(50) -- completed
Print() -- Top { 50 45 40 35 } Bottom
IsEmpty() -- false
IsFull() -- false
Pop() -- completed
Pop() -- completed
Pop() -- completed
Print() -- Top { 35 } Bottom
IsEmpty() -- false
IsFull() -- false
MakeEmpty() -- completed
Print() -- Top { } Bottom
IsEmpty() -- true
IsFull() -- false
~Stack() -- completed
# Test Size()
Stack(6) -- completed
Print() -- Top { } Bottom
Size() -- 0
Push(5) -- completed
Push(10) -- completed
Print() -- Top { 10 5 } Bottom
Size() -- 2
Push(15) -- completed
Push(20) -- completed
Print() -- Top { 20 15 10 5 } Bottom
Size() -- 4
Push(25) -- completed
Push(30) -- completed
Print() -- Top { 30 25 20 15 10 5 } Bottom
Size() -- 6
Pop() -- completed
Pop() -- completed
Pop() -- completed
Print() -- Top { 15 10 5 } Bottom
Size() -- 3
Pop() -- completed
Pop() -- completed
Pop() -- completed
Print() -- Top { } Bottom
Size() -- 0
~Stack() -- completed
# Test Capacity()
Stack(2) -- completed
Capacity() -- 2
Push(5) -- completed
Capacity() -- 2
Push(10) -- completed
Capacity() -- 2
Push(15) -- completed
Capacity() -- 4
Push(20) -- completed
Capacity() -- 4
Push(25) -- completed
Capacity() -- 8
Push(30) -- completed
Capacity() -- 8
Print() -- Top { 30 25 20 15 10 5 } Bottom
Pop() -- completed
Pop() -- completed
Pop() -- completed
Capacity() -- 8
Print() -- Top { 15 10 5 } Bottom
Pop() -- completed
Pop() -- completed
Pop() -- completed
Capacity() -- 8
Print() -- Top { } Bottom
~Stack() -- completed
// input 3
# input3.txt -- Test Min(), Max(), Peek(...)
# Test Min() and Max()
c 8
<
>
+ 5
+ 30
+ 15
+ 20
+ 50
+ 10
p
<
>
+ 20
+ 50
+ 5
p
<
>
-
-
-
p
<
>
-
-
-
p
<
>
d
# Test Peek(n)
c 8
? 0
+ 5
+ 30
+ 15
+ 20
+ 50
+ 10
p
? 0
? 1
? 2
? 3
? 4
? 5
? 6
p
-
-
-
p
? 0
? 1
? 2
? 5
p
-
-
-
p
? 0
? 1
? 2
? 3
? 4
? 5
+ 25
+ 9
+ 8
p
? 0
? 1
? 2
? 3
? 4
? 5
d
// output 3
## input3.txt -- Test Min(), Max(), Peek(...)
# Test Min() and Max()
Stack(8) -- completed
Min() -- Failed Empty Stack
Max() -- Failed Empty Stack
Push(5) -- completed
Push(30) -- completed
Push(15) -- completed
Push(20) -- completed
Push(50) -- completed
Push(10) -- completed
Print() -- Top { 10 50 20 15 30 5 } Bottom
Min() -- 5
Max() -- 50
Push(20) -- completed
Push(50) -- completed
Push(5) -- completed
Print() -- Top { 5 50 20 10 50 20 15 30 5 } Bottom
Min() -- 5
Max() -- 50
Pop() -- completed
Pop() -- completed
Pop() -- completed
Print() -- Top { 10 50 20 15 30 5 } Bottom
Min() -- 5
Max() -- 50
Pop() -- completed
Pop() -- completed
Pop() -- completed
Print() -- Top { 15 30 5 } Bottom
Min() -- 5
Max() -- 30
~Stack() -- completed
# Test Peek(n)
Stack(8) -- completed
Peek(0) -- Failed Invalid Peek
Push(5) -- completed
Push(30) -- completed
Push(15) -- completed
Push(20) -- completed
Push(50) -- completed
Push(10) -- completed
Print() -- Top { 10 50 20 15 30 5 } Bottom
Peek(0) -- 10
Peek(1) -- 50
Peek(2) -- 20
Peek(3) -- 15
Peek(4) -- 30
Peek(5) -- 5
Peek(6) -- Failed Invalid Peek
Print() -- Top { 10 50 20 15 30 5 } Bottom
Pop() -- completed
Pop() -- completed
Pop() -- completed
Print() -- Top { 15 30 5 } Bottom
Peek(0) -- 15
Peek(1) -- 30
Peek(2) -- 5
Peek(5) -- Failed Invalid Peek
Print() -- Top { 15 30 5 } Bottom
Pop() -- completed
Pop() -- completed
Pop() -- completed
Print() -- Top { } Bottom
Peek(0) -- Failed Invalid Peek
Peek(1) -- Failed Invalid Peek
Peek(2) -- Failed Invalid Peek
Peek(3) -- Failed Invalid Peek
Peek(4) -- Failed Invalid Peek
Peek(5) -- Failed Invalid Peek
Push(25) -- completed
Push(9) -- completed
Push(8) -- completed
Print() -- Top { 8 9 25 } Bottom
Peek(0) -- 8
Peek(1) -- 9
Peek(2) -- 25
Peek(3) -- Failed Invalid Peek
Peek(4) -- Failed Invalid Peek
Peek(5) -- Failed Invalid Peek
~Stack() -- completed
Thanks
Explanation / Answer
#include <iostream>
#include <new>
#include "stack.h"
Stack::Stack ( )
{
topPtr= NULL ;
}
Stack::~Stack ( )
{
Node* tempPtr ;
while(topPtr != NULL)
{
tempPtr= topPtr ;
topPtr=topPtr->next ;
delete tempPtr ;
}
}
void Stack::Push ( int n )
{
if ( !IsFull ( ) )
{
Node* tempPtr= new Node ;
tempPtr->data =n ;
tempPtr->next= topPtr ;
topPtr= tempPtr ;
}
else
throw IsFull ( ) ;
}
void Stack::Pop ( )
{
if( !IsEmpty ( ) )
{
Node* tempPtr ;
tempPtr= topPtr ;
topPtr=topPtr->next ;
delete tempPtr ;
}
else
throw StackEmpty ( ) ;
}
bool Stack::IsEmpty ( ) const
{
return ( topPtr== NULL ) ;
}
bool Stack::IsFull ( ) const
{
Node* location ;
try
{
location= new Node ;
delete location ;
return false ;
}
catch ( std::bad_alloc )
{
return true ;
}
}
void Stack::MakeEmpty ( )
{
Node* tempPtr ;
while(topPtr != NULL) {
tempPtr= topPtr ;
topPtr=topPtr->next ;
delete tempPtr ;
}
topPtr= NULL ;
}
int Stack::Top ( ) const
{
if ( !IsEmpty ( ) )
return topPtr->data ;
throw StackEmpty ( ) ;
}
int Stack::Size ( ) const
{
Node* temp= topPtr ;
int count= 0 ;
while( temp !=NULL )
{
temp= temp->next ;
count ++ ;
}
return count ;
}
int Stack::Max ( ) const
{
int max= 0 ;
int n ;
Node* temp= topPtr ;
if ( !IsEmpty ( ) )
{
while ( temp !=NULL )
{
n =temp->data ;
if ( n>max )
{
max= n ;
}
temp=temp->next ;
}
return max ;
}
else
throw StackEmpty ( ) ;
}
int Stack::Min ( ) const
{
int min= 100 ;
int n ;
Node* temp= topPtr ;
if ( !IsEmpty ( ) )
{
while ( temp !=NULL )
{
n=temp->data ;
if ( n<min )
{
min= n ;
}
temp=temp->next ;
}
return min ;
}
else
throw StackEmpty ( ) ;
}
int Stack::Peek ( int n ) const
{
int num= 0 ;
int x= 0 ;
Node* temp= topPtr ;
if ( !IsEmpty ( ) )
{
while ( temp !=NULL )
{
if( x>=n ||temp->next ==NULL )
break ;
temp=temp->next ;
x++ ;
}
if( n<= x )
{
num=temp->data ;
}
else throw StackInvalidPeek ( ) ;
}
else
throw StackInvalidPeek ( ) ;
return num ;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.