Working With Stacks (COMPLETE EITHER 2B OR 2C) Complete the following exercises
ID: 3808538 • Letter: W
Question
Working With Stacks (COMPLETE EITHER 2B OR 2C)
Complete the following exercises using the cs20::Stack class presented in class.
1. Create a new method on a Stack that determines if all the values on the Stack are smaller than the passed value. For example, for a stack containing top- (1) (1) (2) (3) (5) (5) (2) , allSmaller( 3 ) should return false because there are values on the Stack bigger than 3. On the other hand, for a stack containing top- (10) (11) (20) (30) (50) (15) (12) , allSmaller( 100 ) should return true because all the values on the stack are smaller than 100. If the stack is empty, this new operation should return true.
This new operation of the Stack class should have the signature:
Because it has been marked const, this method is saying that it is read-only. When your implementation runs, you won't be able to actually change any data members of the Queue passed to your method. Create a test driver program that exercises each of these exercises to satisfy yourself that your implementation is correct. For example, you should print the Queue before and after invoking the operation.
TESTING HINT:
Run the methods: push( 3 ); push( 2 ); push( 1 );
Print the queue. What should it look like?
Run the method: allSmaller( 1 ). It should return false. Does it?
Run the method: allSmaller( 0 ). It should return false. Does it?
Run the methods: push( 4 ); push( 1); push( 100 );
Print the queue. What should it look like?
Run the method: allSmaller( 101 ). It should return true. Does it?
Run the methods: pop( ); allSmaller( 5 ). It should return true. Does it?
Run the methods: pop(); pop();
Print the queue. What should it look like?
2. Create a new method on a Stack that determines if how many times a passed value is found on the stack. For example, for a stack containing top- (1) (1) (2) (3) (5) (5) (2) , count( 5 ) should return 2 because it is there just once on the stack. On the other hand, for a stack containing top- (1) (1) (2) (3) (5) (5) (2) , count( 12 ) should return 0 because there are no values on the stack that equal 12.
This new operation of the Stack class should have the signature:
Because it has been marked const, this method is saying that it is read-only. When your implementation runs, you won't be able to actually change any data members of the Stack passed to your method. Create a test driver program that exercises each of these exercises to satisfy yourself that your implementation is correct. For example, you should print the Stack before and after invoking the operation.
TESTING HINT:
Run the methods: push( 3 ); push( 2 ); push( 1 );
Print the queue. What should it look like?
Run the method: count( 1 ). It should return 1. Does it?
Run the method: count( 0 ). It should return 0. Does it?
Run the methods: push( 4 ); push( 100 ); push( 1 );
Print the queue. What should it look like?
Run the method: count( 1 ). It should return 2. Does it?
Run the method: count( 100 ). It should return 1. Does it?
Run the methods: pop(); pop();
Print the queue. What should it look like?
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
here's the code:
StackMenu.cpp
// Menu.cpp : Defines the entry point for the console application.
//
#include <iostream>
#include "Stack.h"
#include "EmptyStack.h"
#include "StackNode.h"
#include "Stack.cpp"
#include "StackNode.cpp"
using namespace std;
using namespace cs20;
enum CHOICE {MAKEEMPTY, PUSH, ISEMPTY, POP, TOP, TOPANDPOP, QUIT, PRINT };
CHOICE menu();
int main(int argc, char* argv[]) {
int value;
Stack<int> stack;
CHOICE choice;
do {
choice = menu();
switch( choice ) {
case MAKEEMPTY:
stack.makeEmpty();
break;
case ISEMPTY:
if (stack.isEmpty()) {
cout << "stack is empty" << endl;
}
else {
cout << "stack is not empty" << endl;
}
break;
case TOP:
try {
value = stack.top();
cout << "Here's the value on top: ";
cout << value << endl;
} catch( EmptyStack es ) {
cout << "You silly... don't try topping an empty stack!" << endl;
}
break;
case POP:
try {
stack.pop();
} catch( EmptyStack es ) {
cout << "You silly... don't try popping an empty stack!" << endl;
}
break;
case PUSH:
cout << "Please provide int to push: ";
cin >> value;
stack.push( value );
break;
case TOPANDPOP:
try {
value = stack.topAndPop();
cout << "Here's the value on top that got popped: ";
cout << value << endl;
} catch( EmptyStack es ) {
cout << "You silly... don't try topAndPopping an empty stack!" << endl;
}
break;
case PRINT:
stack.printStack( cout );
cout << endl;
break;
case QUIT:
break;
}
} while (choice != QUIT);
return( 0 );
}
CHOICE menu() {
char choice;
CHOICE result;
cout << "(M)akeEmpty I(s)Empty p(U)sh p(O)p (T)op top(A)ndpop (P)rint (Q)uit: " << endl;
cin >> choice;
switch( choice ) {
case 'A':
case 'a':
result = TOPANDPOP;
break;
case 'M':
case 'm':
result = MAKEEMPTY;
break;
case 'S':
case 's':
result = ISEMPTY;
break;
case 'U':
case 'u':
result = PUSH;
break;
case 'O':
case 'o':
result = POP;
break;
case 'T':
case 't':
result = TOP;
break;
case 'Q':
case 'q':
result = QUIT;
break;
case 'P':
case 'p':
result = PRINT;
break;
}
return( result );
}
void sample() {
Stack<int> s1;
Stack<int> s2;
cout << "making s1" << endl;
s1.push( 1 );
s1.push( 2 );
cout << "print s1" << endl;
s1.printStack( cout );
cout << endl;
cout << "s2 = s1" << endl;
s2 = s1;
cout << "print s2" << endl;
s2.printStack( cout );
cout << endl;
s1.pop();
cout << "pop s1" << endl;
cout << "print s2" << endl;
s2.printStack( cout );
cout << endl;
cout << "print s1" << endl;
s1.printStack( cout );
cout << endl;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
StackNode.cpp
#ifndef STACKNODE_CPP
#define STACKNODE_CPP
#include "StackNode.h"
namespace cs20 {
template <class Object>
StackNode<Object>::StackNode( const Object& theElement,
StackNode<Object> * node ) {
element = theElement;
next = node;
}
template <class Object>
const Object& StackNode<Object>::getElement() const {
return( element );
}
template <class Object>
StackNode<Object>* StackNode<Object>::getNext() const {
return( next );
}
template <class Object>
void StackNode<Object>::setNext( StackNode<Object>* node ) {
next = node;
}
}
#endif
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Stack.cpp
#ifndef STACK_CPP
#define STACK_CPP
#include "Stack.h"
namespace cs20 {
template <class Object>
Stack<Object>::Stack() {
topNode = nullptr;
}
template <class Object>
Stack<Object>::Stack( const Stack<Object>& rhs ) {
topNode = nullptr;
*this = rhs;
}
template <class Object>
Stack<Object>::~Stack() {
makeEmpty();
delete topNode;
}
template <class Object>
bool Stack<Object>::isEmpty() const {
return( (topNode == nullptr) );
}
template <class Object>
void Stack<Object>::makeEmpty() {
while (!isEmpty()) {
pop();
}
}
template <class Object>
void Stack<Object>::push( const Object& data ) {
StackNode<Object>* newNode = new StackNode<Object>( data, topNode );
topNode = newNode;
}
template <class Object>
void Stack<Object>::pop() {
if (isEmpty()) {
throw EmptyStack();
}
StackNode<Object> *oldTop = topNode;
topNode = topNode->getNext();
delete oldTop;
}
template <class Object>
const Object& Stack<Object>::top( ) const {
if (isEmpty()) {
throw EmptyStack();
}
StackNode<Object> node = *topNode;
return( node.getElement() );
}
template <class Object>
Object Stack<Object>::topAndPop( ) {
Object o = top();
pop();
return( o );
}
// Deep copy of linked Stack
template <class Object>
const Stack<Object>& Stack<Object>::operator =( const Stack<Object>& rhs ) {
if (this != &rhs) {
makeEmpty();
if (!(rhs.isEmpty())) {
StackNode<Object> * rhsTopNode = rhs.topNode;
StackNode<Object> * myTopNode = new StackNode<Object>( rhsTopNode->getElement() );
topNode = myTopNode;
rhsTopNode = rhsTopNode->getNext();
while (rhsTopNode != nullptr) {
myTopNode->setNext( new StackNode<Object>( rhsTopNode->getElement() ) );
myTopNode = myTopNode->getNext();
rhsTopNode = rhsTopNode->getNext();
}
}
}
return( *this );
}
template <class Object>
std::ostream& Stack<Object>::printStack( std::ostream& outs ) const {
if (isEmpty()) {
outs << "Empty Stack";
}
else {
outs << "TOP: ";
StackNode<Object> * node = topNode;
while (node != nullptr) {
outs << node->getElement();
outs << " "; /// for visual alignment
node = node->getNext();
}
}
return( outs );
}
}
#endif
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Stack.h
#ifndef STACK_H
#define STACK_H
#include <iostream>
#include "StackNode.h"
#include "EmptyStack.h"
namespace cs20 {
template <class Object>
class Stack {
public:
Stack();
Stack( const Stack& rhs );
~Stack();
bool isEmpty() const;
void makeEmpty();
void push( const Object& data );
void pop();
const Object& top() const;
Object topAndPop();
std::ostream& printStack( std::ostream& outs ) const;
const Stack& operator =( const Stack& rhs );
private:
StackNode<Object> * topNode;
};
}
#endif
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
StackNode.h
#ifndef STACKNODE_H
#define STACKNODE_H
#include <iostream>
namespace cs20 {
template <class Object>
class StackNode {
public:
StackNode( const Object& theElement = Object(), StackNode * node = nullptr );
const Object& getElement() const;
StackNode* getNext() const;
void setNext( StackNode* node );
private:
Object element;
StackNode* next;
};
}
#endif
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
EmptyStack.cpp
#include "EmptyStack.h"
namespace cs20 {
EmptyStack::EmptyStack( const std::string& msg ) : std::logic_error( msg.c_str() ) {}
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
EmptyStack.h
#ifndef EMPTYSTACK_H
#define EMPTYSTACK_H
#include <iostream>
#include <string>
namespace cs20 {
class EmptyStack : public std::logic_error {
public:
EmptyStack( const std::string& msg = "" );
};
}
#endif
Explanation / Answer
#include <iostream>
#include "Stack.h"
#include "EmptyStack.h"
#include "StackNode.h"
#include "Stack.cpp"
#include "StackNode.cpp"
using namespace std;
using namespace cs20;
enum CHOICE {MAKEEMPTY, PUSH, ISEMPTY, POP, TOP, TOPANDPOP, QUIT, PRINT };
CHOICE menu();
int main(int argc, char* argv[]) {
int value;
Stack<int> stack;
CHOICE choice;
do {
choice = menu();
switch( choice ) {
case MAKEEMPTY:
stack.makeEmpty();
break;
case ISEMPTY:
if (stack.isEmpty()) {
cout << "stack is empty" << endl;
}
else {
cout << "stack is not empty" << endl;
}
break;
case TOP:
try {
value = stack.top();
cout << "Here's the value on top: ";
cout << value << endl;
} catch( EmptyStack es ) {
cout << "You silly... don't try topping an empty stack!" << endl;
}
break;
case POP:
try {
stack.pop();
} catch( EmptyStack es ) {
cout << "You silly... don't try popping an empty stack!" << endl;
}
break;
case PUSH:
cout << "Please provide int to push: ";
cin >> value;
stack.push( value );
break;
case TOPANDPOP:
try {
value = stack.topAndPop();
cout << "Here's the value on top that got popped: ";
cout << value << endl;
} catch( EmptyStack es ) {
cout << "You silly... don't try topAndPopping an empty stack!" << endl;
}
break;
case PRINT:
stack.printStack( cout );
cout << endl;
break;
case QUIT:
break;
}
} while (choice != QUIT);
return( 0 );
}
CHOICE menu() {
char choice;
CHOICE result;
cout << "(M)akeEmpty I(s)Empty p(U)sh p(O)p (T)op top(A)ndpop (P)rint (Q)uit: " << endl;
cin >> choice;
switch( choice ) {
case 'A':
case 'a':
result = TOPANDPOP;
break;
case 'M':
case 'm':
result = MAKEEMPTY;
break;
case 'S':
case 's':
result = ISEMPTY;
break;
case 'U':
case 'u':
result = PUSH;
break;
case 'O':
case 'o':
result = POP;
break;
case 'T':
case 't':
result = TOP;
break;
case 'Q':
case 'q':
result = QUIT;
break;
case 'P':
case 'p':
result = PRINT;
break;
}
return( result );
}
void sample() {
Stack<int> s1;
Stack<int> s2;
cout << "making s1" << endl;
s1.push( 1 );
s1.push( 2 );
cout << "print s1" << endl;
s1.printStack( cout );
cout << endl;
cout << "s2 = s1" << endl;
s2 = s1;
cout << "print s2" << endl;
s2.printStack( cout );
cout << endl;
s1.pop();
cout << "pop s1" << endl;
cout << "print s2" << endl;
s2.printStack( cout );
cout << endl;
cout << "print s1" << endl;
s1.printStack( cout );
cout << endl;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.