QuestionQuestion

1. Problem description
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 PreviewSolution 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.

$50.00
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available C-Family Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats