myStack.cpp

#include #include "myStack.h"

using namespace std;

/* * Constructor * Usage: myStack(maxSz); * ------------------------- * A new stack variable is initialized. The initialized * stack is made empty. maxSz is used to determine the * maximum number of character that can be held in the * stack. */

myStack::myStack(int maxSz) { // TODO }

/* Destructor * Usage: delete ptr * ----------------------- * This frees all memory associated with the stack. */

myStack::~myStack() { // TODO }

/* * Functions: push, pop * Usage: s1.push(element); element = s1.pop(); * -------------------------------------------- * These are the fundamental stack operations that add an element to * the top of the stack and remove an element from the top of the stack. * A call to pop on an empty stack or to push on a full stack * is an error. Make use of isEmpty()/isFull() (see below) * to avoid these errors. */

void myStack::push(int element) { // TODO }

int myStack::pop() { // TODO }

/* * Functions: isEmpty, isFull * Usage: if (s1.isEmpty()) ... * ----------------------------------- * These return a true value if the stack is empty * or full (respectively). */

bool myStack::isEmpty() const { // TODO }

bool myStack::isFull() const { // TODO }

mystack.h

#ifndef _MYSTACK_H_ #define _MYSTACK_H_

class myStack { public: myStack(int maxSz); ~myStack(); void push(int element); int pop(); bool isEmpty() const; bool isFull() const;

private: int *contents; /*Dynamic initiate (C++ keyword new) the holder array*/ int top; /*Index in the array of the top element*/ int maxSize; /*Max number of elements could be in this stack*/ };

#endif

myStackTest.cpp

include #include "myStack.h"

using namespace std;

void postfixTest() { myStack operandStack(100); cout > inputHolder; // TODO } }

int main() { cout > testSize; myStack testStack(testSize); cout > userChoice; if(userChoice == 'e') break; switch (userChoice) { case 'p': if(!testStack.isFull()) { cout > userInt; testStack.push(userInt); } else cout

cout

myQueue.h

#ifndef _MYQUEUE_H_ #define _MYQUEUE_H_

using namespace std;

template class myQueue { public: myQueue(int maxSz); ~myQueue(); void enqueue(T item); T dequeue(); int currentSize(); bool isEmpty(); bool isFull();

private: T *contents; /*Dynamic initiate (C++ keyword new) the holder array*/ int front,rear; /*Index in the array of the front and rear element*/ int arrayLength; /*The length of the contents holder array*/ /* Keep in mind that the Queue will only hold up to (arrayLength - 1) elements*/ };

template myQueue::myQueue(int maxSz) { // TODO }

template myQueue::~myQueue() { // TODO }

template void myQueue::enqueue(T item) { // TODO }

template T myQueue::dequeue() { // TODO }

template int myQueue::currentSize() { // TODO }

template bool myQueue::isEmpty() { // TODO }

template bool myQueue::isFull() { // TODO }

#endif

queueTest.cpp

#include #include "myQueue.h"

using namespace std;

int main() { cout > capacity; myQueue testIntQ(capacity); while(1) { cout > userOption; if(userOption == 's') break; switch(userOption) { case 'e': if(!testIntQ.isFull()) { cout > val; testIntQ.enqueue(val); } else cout Both the implementations for the stack and queue are supposed to be array-based in this assignment. 1. (40') In myStack.cpp, implement the member functions of the class myStack, which is the class for integer stacks. 2. (20') In stackTest.cpp, complete the implementation of function postfixTest(), which use an integer stack to evaluate post-fix expressions. For simplicity, you can assume the post-fix expression is input character by character (i.e., not an entire string), and each operand is a non-negative, single-digit integer (i.e., 0,1,...,9). However, you are supposed to detect invalid/ illegal post-fix expression input, e.g., 4 5 +. 3. (40') In myQueue.h, implement the queue class template, myQueue. Keep in mind, the arrayLength needs to be one more than the capacity of the queue. Also, under this implementation, make sure your calculation of currentSize is correct, and the conditions for Full and Empty" are correct. One shortcut could be: once you make sure currentSize() is implemented correctly, you might use it in isFull () and isEmpty(), and the number of elements in the queue must range from 0 to arrayLength - 1. Compiling: For the stack part, you will need to compile myStack.cpp and stackTest.cpp separately to two .o files and then link the together to the executable. For the queue part, you can directly compile queueTest.cpp to the executable. Two PDF guides in TRACS might be helpful, if you are not familiar with these in the Linux environment using the g++ compiler. Sample Output for stackTest: Testing the basic functions of the stack... Please enter the max capacity of the testStack: 3 Testing... Please enter 'p' for push, 'o' for pop, 'e' for exit: p Please enter the integer you would like to push: 5 Please enter 'p' for push, 'o' for pop, 'e' for exit: p Please enter the integer you would like to push: 7 Please enter 'p' for push, 'o' for pop, 'e' for exit: p Please enter the integer you would like to push: 9 Please enter 'p' for push, 'o' for pop, 'e' for exit: p Nothing has been pushed in. The stack is full! Please enter 'p' for push, 'o' for pop, 'e' for exit: 0 9 has been popped out Please enter 'p' for push, 'o' for pop, 'e' for exit: 0 7 has been popped out Please enter 'p' for push, 'o' for pop, 'e' for exit: 0 5 has been popped out Please enter 'p' for push, 'o' for pop, 'e' for exit: 0 Nothing has been popped out. The stack is empty! Please enter 'p' for push, 'o' for pop, 'e' for exit: e Now, start to use a stack to evaluate postfix expressions... Please enter the operands (integers 1~9) and operators (+, -, *, 1) one by one... and enter '=' to indicate the end of the expression and to output the result. The entered post-fix expression results in 37 Sample Output for queueTest: Testing the template myQueue, try an integer queue as an example... Please enter the max size of the int queue: 2 Please enter 'e' for enqueue, 'd' for dequeue, and 's' for stop. Please enter the integer you want to enqueue: 10 Please enter 'e' for enqueue, 'd' for dequeue, and 's' for stop. Please enter the integer you want to enqueue: 20 Please enter 'e' for enqueue, 'd' for dequeue, and 's' for stop. Cannot enqueue. The queue is full. Please enter 'e' for enqueue, 'd' for dequeue, and 's' for stop. 10 has been popped out. Please enter 'e' for enqueue, 'd' for dequeue, and 's' for stop. 20 has been popped out. Please enter 'e' for enqueue, 'd' for dequeue, and 's' for stop. Cannot pop. The queue is empty. Please enter 'e' for enqueue, 'd' for dequeue, and 's' for stop