## Question

An integer stack is a LIFO (last in, first out) data structure that serves to collect integers, providing two principal operations: push (i.e. operator<<(int e)), which adds an integer into the collection, and pop(i.e. operator>>(int &e)), which removes the last integer that was pushed. The data type INTSTK can be implemented with a linear data structure by using an integer pointer to a piece of memory that can store at most m elements. The head file intstk.h describes the data type INTSTK as follows:

struct INTSTK{

int *const e; //memory allocated to store integers

const int m; //maximum number of integers the stack can hold

int t; //top indicator or number of integers in current stack;

};

//initialize a new INTSTK pointed by p which can store at most m integers

void initSTK (INTSTK *const p, int m);

//initialize a new INTSTK pointed by p with integers the same as in the existed INTSTK s

void initSTK (INTSTK *const p, const INTSTK &s);

//get maximum number m of an INTSTK pointed by p

int size (const INTSTK *const p);

//get the top indicator t of an INTSTK pointed by p

int howMany (const INTSTK *const p);

/get the integer at location x in the INTSTK pointed by p where x==0 means the deepest one

int getelem (const INTSTK *const p, int x);

//push e onto the top of an INTSTK pointed by p, and the return value is p

INTSTK *const push(INTSTK *const p, int e);

//pop the top integer into e from the INTSTK pointed by p, and the return value is p

INTSTK *const pop(INTSTK *const p, int &e);

//assign INTSTK s to an INTSTK pointed by p, and the return value is p

INTSTK *const assign(INTSTK *const p, const INTSTK &s);

//print out all integers in the INTSTK pointed by p

void print(const INTSTK *const p);

//destroy the INTSTK pointed by p

void destroySTK(INTSTK *const p);

An integer stack is a LIFO (last in, first out) data structure that serves to collect integers, providing two principal operations: push (i.e. operator<<(int e)), which adds an integer into the collection, and pop(i.e. operator>>(int &e)), which removes the last integer that was pushed. The data type STACK can be implemented with a linear data structure by using an integer pointer to a piece of memory that can store at most m elements. The head file stack.h describes the data type STACK as follows, which is similar the above INTSTK:

class STACK{

int *const e; //memory allocated to store integers

const int m; //maximum number of integers the stack can contain

int t; //top indicator or number of integers in current stack

public:

STACK(int m); //create a stack which can store at most m elements

STACK(const STACK&s); //deep-copy constructor of stack s

virtual int size ( ) const; //get maximum number m

virtual operator int ( ) const; //get top indicator t

virtual int operator[ ] (int x) const; //get integer at location x in the stack

virtual STACK& operator<<(int e); //push e into the stack

virtual STACK& operator>>(int &e); //pop an integer to e from the stack

virtual STACK& operator=(const STACK&s); //deep-copy assignment of stacks

virtual void print( ) const; //print out all integers in the stack

virtual ~STACK( ); //destroy the stack

};

An integer queue is a FIFO (first in, first out) data type which can be implemented with two integer stacks. The two principal operations enqueue (i.e. QUEUE& operator<<(int e)) and dequeue (i.e. operator>>(int &e)) of queue can be implemented via push and pop operations with two stacks. The data type QUEUE is derived from a stack while using another stack as data member. Please include the head file queue.h as follows:

class QUEUE: public STACK{

STACK stk;

public:

QUEUE(int m); //create a queue which can store at most 2m elements

QUEUE(const QUEUE&q); //deep-copy constructor of queue q

virtual operator int ( ) const; //get number of elements in queue

virtual int operator[ ] (int x) const; //get element at location x in the queue

virtual QUEUE& operator<<(int e); //enqueue e into queue

virtual QUEUE& operator>>(int &e); //dequeue an integer to e from queue

virtual QUEUE& operator=(const QUEUE&s); //deep-copy assignment of queue

virtual void print( ) const; //print the queue

virtual ~QUEUE( ); //destroy the queue

};

The project should include at least 6 files: (1) intstk.h and intstk.cpp which are used to implement INTSTK; (2) stack.h and stack.cpp which are used to implement STACT; (3) queue.h and queue.cpp which are used to implement QUEUE. In addition, you should write a main function to test the functions defined in INTSTK, STACK and QUEUE. You should implement QUEUE which will at most hold 2m integers.

2. Algorithm design

Please describe your design idea, for example, the architecture of your algorithm, the partition method of complex functions into simpler sub-functions, the interface of above functions, and the relations between these functions. Please draw program flow diagram for each function.

3. Algorithm development

Please describe your compiler or IDE tools，and your process of coding, debugging and testing.

4. Algorithm testament

According to the problem description, please construct test instances, test your program and check the results of your tests.

5. Conclusion

Please give a description of whether you have achieved the objective of solving the given problem, and what are the problems and creative ideas in your problem solving.

Please describe what are the short comes or disadvantages of your algorithm, and the possible way to overcome these defects in future.

6. Experiences and tastes

Please list out the problems you have met in your analysis, design, and coding processes, and describe how you solved these problems.

Please simply describe your tastes and feelings in your programming experience.

7. Source codes and remarks

Please list your program files, print them as an appendix，and remark each function in the program.

## Solution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

#include "stack.h"#include <iostream>

using namespace std;

STACK::STACK(int m): e{new int[m]}, m {m}, t{0} {

}

STACK::STACK(const STACK& o) : e{new int[o.m]}, m {0}, t{o.t} {

for (int i = 0; i < t; i++) {

e[i] = o.e[i];

}

}

STACK::~STACK() {

delete [] e;

}

STACK& STACK::operator<<(int e) {

if (t < m) {

// insdert to the end of stack

this->e[t] = e;

t++;

}

return *this;

}

STACK& STACK::operator=(const STACK& s) {

if (this == &s) {

return *this;

}

// copy all stack

for (int i = 0; i < m && i < s.t; i++) {

e[i] = s.e[i];

}

t = s.t;

return *this;

}

#include <iostream>

using namespace std;

STACK& STACK::operator>>(int& e) {

if (t > 0) {

// decrease the counter

t--;

// get the right number

e = this->e[t];

}

return *this;

}...

By purchasing this solution you'll be able to access the following files:

Solution.zip.