Project 2: Stack and Queue Solution

Note: This assignment is used to assess the = required=20 outcomes for the course, as outlined in the course syllabus. These = outcomes are:
    1. use of arrays and pointers in the solution of programming = problems=20 using C++=20
    2. create and use classes within the C++ programming language=20
    3. create, compile, and execute C++ programs within the Unix=20 environment, using the Object-Oriented design model=20
    4. program using C++ techniques: composition of objects, = operator=20 overloads, dynamic memory allocation, inheritance and = polymorphism, and=20 file I/O=20
    5. program using C++ techniques: composition of objects, = templates,=20 preprocessor directives, and basic data structures.
These will be assessed using the following rubric:
Rubric for Outcome v.
I
E
H
 
Key:
  I =3D=20 ineffective
  E =3D effective
  H =3D = highly=20 effective
v.
Templates, Basic Data Structures, Preprocessor = Directives, and=20 Composition
-
-
-


In order to earn a course grade of C- or better, the assessment = must=20 result in Effective or Highly Effective for each outcome.=20
Educational Objectives: After completing this assignment the = student=20 should have the following knowledge, ability, and skills:
    • Define the concept of Generic Container=20
    • Define the ADT Stack with elements of type T and maximum size N=20
    • Give examples of the use of Stack in computing=20
    • Describe an implementation plan for generic Stack as a class = template=20 Stack<T,N> based on an array of T objects=20
    • Code the implementation for Stack<T,N> using the = plan=20
    • Define the ADT Queue with elements of type T=20
    • Give examples of the use of Queue in computing=20
    • Describe an implementation plan for generic Queue as a class = template=20 Queue<T> based on dynamically allocated links = containing=20 T objects=20
    • Code the implementation for Stack<T,N> using the = plan=20
    • Describe an implementation plan for Stack<T,N> = based on=20 dynamically allocated links containing T objects=20
    • Explain why it is impractical to implement Queue<T> = using=20 an array
Operational Objectives: Create two generic container = classes=20 fsu::TStack<T,N> and fsu::TQueue<T> that = satisfy=20 the interface requirements given below, along with appropriate test = harnesses=20 for these classes.
Deliverables: Five files tstack.h,=20 tqueue.h, ftstack.cpp, and ftqueue.cpp.
Abstract Data Types
An abstract data type, abbreviated ADT, consists of three = things:=20
    1. A set of elements of some type T=20
    2. Operations that may modify the set or return values associated = with the=20 set=20
    3. Rules of behavior, or axioms, that determine how the operations = interact=20
The operations and axioms together should determine a unique = character for=20 the ADT, so that any two implementations should be essentially = equivalent. (The=20 word isomorphic is used to give precision to "essentially = equivalent".=20 We'll look at this in the next course.)
Stacks and Queues
The stack and queue are ADTs that are used in many=20 applications and have roots that pre-date the invention of high-level = languages.=20 Conceptually, stack and queue are sets of data that can be expanded, = contracted,=20 and accessed using very specific operations. The stack models the = "LIFO", or=20 last-in, first-out, rule, and the queue models the "FIFO", or first-in,=20 first-out rule. The actual names for the stack and queue operations may = vary=20 somewhat from one description to another, but the behavior of the = abstract stack=20 and queue operations is well known and unambiguously understood = throughout=20 computer science. Stacks and queues are important in many aspects of = computing,=20 ranging from hardware design and I/O to algorithm control structures. =
Typical uses of ADT Stack are (1) runtime environment for modern = programming=20 languages (facilitating recursive function calls, among other things), = (2)=20 control of the depth first search and backtracking search algorithms, = (3)=20 hardware evaluation of postfix expressions, and (4) various compiler = operations,=20 such as converting expressions from infix to postfix.
Typical uses of ADT Queue are (1) buffers, without which computer=20 communication would be impossible, (2) control of algorithms such as = breadth=20 first search, and (3) simulation modelling of systems as diverse as=20 manufacturing facilities, customer service, and computer operating = systems.
Abstract Stack Interface
The stack abstraction has the following operations and behavior:
    • Push(t) Inserts the element t into = the=20 stack=20
    • Pop() Removes the last-inserted element; undefined = when=20 stack is empty=20
    • Top() Returns the last-inserted element; undefined = when=20 stack is empty=20
    • Empty() Returns true iff the stack has no elements =
    • Size() Returns the number of elements in the stack =
Abstract Queue Interface
The queue abstraction has the following operations and behavior:
    • Push(t) Inserts the element t into = the=20 queue=20
    • Pop() Removes the first-inserted element; = undefined when=20 queue is empty=20
    • Front() Returns the first-inserted element; = undefined when=20 queue is empty=20
    • Empty() Returns true iff the queue has no elements =
    • Size() Returns the number of elements in the queue =
Application: Converting Infix to Postfix Notation
As one example of the use of stacks and queues in computing, consider = the=20 following function that illustrates an algorithm for converting = arithmetic=20 expressions from infix to postfix notation:
...
#include <tqueue.h>
#include <tstack.h>
...
typedef fsu::TQueue < Token > TokenQueue;
typedef fsu::TStack < Token > TokenStack;
// a Token is either an operand, an operator, or a left or right =
parenthesis
...
bool i2p (TokenQueue & Q1, TokenQueue & Q2)
// converts infix expression in Q1 to postfix expression in Q2
// returns true on success, false if syntax error is encountered
{
   Token L( '(' ), R( ')' );  // left and right parentheses
   TokenStack S;              // algorithm control stack
   Q2.Clear();                // make sure ouput queue is empty
   while (!Q1.Empty())
   {
      if (Q1.Front() =3D=3D L) // next Token is '('
      // push '(' to mark beginning of a parenthesized expression
      {
         S.Push(Q1.Front());
         Q1.Pop();
      }
      else if (Q1.Front().IsOperator()) // next Token is an operator
      {
         // pop previous operators of equal or higher precedence to =
output
         while (!S.Empty() && S.Top() >=3D Q1.Front())
         {
            Q2.Push(S.Top());
            S.Pop();
         }
         // then push new operator onto stack
         S.Push(Q1.Front());
         Q1.Pop();
      }
      else if (Q1.Front() =3D=3D R) // next Token is ')'
      // regurgitate operators for the parenthesized expression
      {
         while (!S.Empty() && !(S.Top() =3D=3D L))
         {
            Q2.Push(S.Top());
            S.Pop();
         }
         if (S.Empty())      // unbalanced parentheses
         {
            std::cout << "** error: too many right parens\n";
            return false;
         }
         S.Pop();            // discard '('
         Q1.Pop();           // discard ')'
      }
      else                   // next Token should be an operand
      // send operand directly to output
      {
         Q2.Push(Q1.Front());
         Q1.Pop();
      }
   }  // end while()
   // regurgitate remaining operators
   while (!S.Empty())
   {
      if (S.Top() =3D=3D L)      // unbalanced parentheses
      {
         std::cout << "** error: too many left parens\n";
         return false;
      }
      Q2.Push(S.Top());
      S.Pop();
   }
   return true;
}  // end i2p()
This is a complex algorithm, but not beyond your capability to = understand.=20 Notice how the algorithm takes into account the different levels of = precedence=20 among operators and the possibility of parenthetical sub-expressions. = Things to=20 make special note of are:
    • A typedef statement is used to define the types = TokenQueue and=20 TokenStack as a queue or stack of tokens; this serves both = programmer=20 convenience and readability of the program.=20
    • Function arguments of type TokenQueue are used as buffers = to pass=20 an expression in to and out from the function.=20
    • A locally declared variable of type TokenStack is used as = the=20 principal control structure for the function.
The stack is used to store the operators of parenthetical = subexpressions as=20 well as operators of one precedence level pending discovery of an = operator of=20 lower precedence. This function is distributed as part of the file=20 in2post.cpp.
Use the distributed executable in2post.x to experiment so = that you=20 understand the roles Stack and Queue play in the algorithm.
TStack Implementation Plan
We will implement the stack abstraction as a C++ class template
template < typename T , size_t N >
TStack;
with the following public methods:
// TStack < T , N > API
void     Push     (const T& t); // push t onto stack; error if full
T        Pop      ();           // pop stack and return removed element; =
error if stack is empty
T&       Top      ();           // return top element of stack; =
error if stack is empty
const T& Top      () const;     // const version
size_t   Size     () const;     // return number of elements in stack
size_t   Capacity () const;     // return storage capacity [maximum =
size] of stack
int      Empty    () const;     // return 1/true if stack is empty, =
0/false if not empty
void     Clear    ();           // make the stack empty
void     Display  (std::ostream& os, char ofc =3D '\0') const; // =
output contents through os
There should be a full complement of self-management features:
TStack             ();              // default =
constructor
TStack             (T fill);        // puts "fill" in each slot of the =
underlying array
TStack             (const TStack&); // copy constructor
~TStack            ();              // destructor
TStack& operator =3D (const TStack&); // assignment operator
The element and size data will be maintained in private variables: =
const size_t capacity_;  // =3D N =3D size of array   - =
fixed during life of stack
T            data_[N];   // array of T objects    - where T objects are =
stored
size_t       size_;      // current size of stack - dynamic during life =
of stack
The class constructors will have responsibility for initializing = variables.=20 Note that capacity_ is a constant, so it must be initialized by = the=20 constructor in the initialization list and it cannot be changed during = the life=20 of a stack object; capacity_ should be given the value passed = in as the=20 second template argument N. Because all class variables are = declared at=20 compile time, the destructor will have no responsibilities. Values = stored in the=20 data_ array and the size_ variable will be correctly=20 maintained by the push and pop operations, using the "upper index" end = of the=20 data as the top of the stack. The data in the stack should always be the = array=20 elements in the range [0..size_), and the element = data_[size_ -=20 1] is the top of the stack (assuming size_ > 0).
Please note that the data_ array is automatically allocated = at=20 compile time and remains allocated during the lifetime of the object. It = is=20 implicitly de-allocated just like any statically declared array, when it = goes=20 out of scope. Thus the underlying "footprint" of the stack object = remains fixed=20 as the size changes, even when the size is changed to zero. There should = be no=20 calls to operators new or delete in this = implementation.
This implementation will have the requirement on clients that the = maximum=20 size required for the stack is known in advance and determined by the = second=20 template argument - see requirements below.
TQueue Implementation Plan
We will implement the queue abstraction as a C++ class template=20 TQueue with the following public methods:
// TQueue < T > API
void      Push    (const T& t); // push t onto queue
T         Pop     ();           // pop queue and return removed element; =
error if queue is empty
T&        Front   ();           // return front element of queue; =
error if queue is empty
const T&  Front   () const;     // const version
size_t    Size    () const;     // return number of elements in queue
int       Empty   () const;     // return 1 if queue is empty, 0 if not =
empty
void      Clear   ();           // make the queue empty
void      Display (std::ostream& os, char ofc =3D '\0') const; // =
output contents through os
There should be a full complement of self-management features:
TQueue             ();              // default =
constructor
TQueue             (const TQueue&); // copy constructor
~TQueue            ();              // destructor
TQueue& operator =3D (const TQueue&); // assignment operator
Unlike Stack, Queue requires access to data at both the front and = back, which=20 makes an array implementation impractical. We will use a linked list=20 implementation using a link class defined as follows:
class Link
{
  Link ( const T& t );  // 1-parameter constructor
  T      element_;
  Link * nextLink_;
  friend class TQueue<T>;
};
Note that all members of class Link are private, which means = a=20 Link object can be created or accessed only inside an = implementation of=20 its friend class TQueue<T>. The only method for class=20 Link is its constructor, whose implementation should just = initialize=20 the two variables. (This can be done inside the class definition, as = shown=20 below.)
The private TQueue variables for this implementation will be = exactly=20 two pointers to links, the first and last links created. Including the=20 definition of the helper class Link, the private section of the = class=20 definition should be like the following (with implementor-chosen private = variable names):
template < typename T >
class TQueue
{
  public:
  ...

  private:
    class Link
    {
      Link ( const T& t ) : element_(t), nextLink_(0) {}
      T      element_;
      Link * nextLink_;
      friend class TQueue<T>;
    };
  Link * firstLink_;
  Link * lastLink_;
};
The class constructor will have responsibility for initializing the = two=20 variables to zero. These two pointers will be zero exactly when there is = no data=20 in the queue (the queue is empty). Links for data will be allocated as = needed by=20 Push() and de-allocated by Pop(). These operations = will also=20 need to re-direct appropriate link pointers in the dynamically allocated = links,=20 and maintain the class variables firstLink_ and = lastLink_=20 correctly pointing to the links containing the first and last elements = of the=20 queue. The destructor should de-allocate all remaining dynamically = allocated=20 links in the queue. The Size() method will have to loop through the = links to=20 count them, whereas the Empty() method can do a simple check for = emptiness of=20 the queue.
Because this implementation relies on dynamically allocated memory, = the=20 container makes no restrictions on the client program as to anticipated = maximum=20 size of the queue.
Procedural Requirements
    1. Create and work within a separate subdirectory = cop3330/proj2.=20 Review the COP 3330 rules found in Introduction/Work Rules.
    2. After starting your log, copy the following files from the course = directory=20 [LIB] into your proj2 directory:
proj2/in2post.cpp
proj2/proj2submit.sh
area51/in2post_s.x
area51/in2post_i.x
area51/ftstack_i.x
area51/ftstack_s.x
area51/ftqueue_i.x
area51/ftqueue_s.x
The naming of these files uses the convention that _s are = compiled=20 for Sun/Solaris and _i are compiled for Intel/Linux. Use one = of the=20 sample client executables to experiment to get an understanding of how = your=20 program should behave.
    3. Define and implement the class template = fsu::TStack<T,N> in=20 the file tstack.h. Be sure to make log entries for your work=20 sessions.
    4. Devise a test client for TStack<T,N> that exercises = the=20 Stack interface for at least one native type and one user-defined type = T. Repair your code as necessary. Put this test client in the = file=20 ftstack.cpp. Be sure to make log entries for your work = sessions.
    5. Define and implement the class template = fsu::TQueue<T> in=20 the file tqueue.h. Be sure to make log entries for your work=20 sessions.
    6. Devise a test client for TQueue<T> that exercises = the Queue=20 interface for at least one native type and one user-defined type = T.=20 Put this test client in the file ftqueue.cpp. Be sure to make = log=20 entries for your work sessions.
    7. Test TStack and TQueue using the supplied = application=20 in2post.cpp. Again, make sure behavior is appropriate and = make=20 corrections if necessary. Log your activities.
    8. Turn in tstack.h, tqueue.h, ftstack.cpp, = and=20 ftqueue.cpp using the proj2submit.sh submit script. =
Warning: Submit scripts do not work on the = program and=20 linprog servers. Use shell.cs.fsu.edu to submit = projects. If=20 you do not receive the second confirmation with the contents of your = project,=20 there has been a malfunction.
Code Requirements and Specifications
    1. Both TStack and TQueue should be a proper type, = with full=20 copy support. That is, they should have a public default constructor,=20 destructor, copy constructor, and assignment operator. Be sure that = you test=20 the copy constructor and assignment operator.
    2. The TStack constructor should create a stack that is empty = but has=20 the capacity to hold N elements, where N is the = second=20 template parameter with type size_t. Note that this parameter = should=20 be given the default value of 100. This has the effect of making a = declaration=20 such as
 
fsu::TStack<int> s; =
 
legal=20 and create a stack with capacity 100.
    3. The TQueue constructor should create an empty queue with = no=20 dynamic memory allocation.
    4. The TQueue<T>::Push(t) operation must dynamically = allocate=20 memory required for storing t in the queue. Similarly, the=20 TQueue<T>::Pop() operation must de-allocate memory used = to=20 store the element being removed from the queue.
    5. As always, the class destructors should de-allocate all dynamic = memory=20 still owned by the object. The stack and queue implementations will be = very=20 different.
    6. Use the implementation plans discussed above. No methods or = variables=20 should be added to these classes, beyond those specified above and in = the=20 implementation plans.
    7. The Display(os, ofc) methods are intended to regurgitate = the=20 contents out through the std::ostream object os. The = second=20 parameter ofc is a single output formatting character that = has the=20 default value '\0'. (The other three popular choices for = ofc=20 are ' ', '\t' and '\n'.) The = implementation of=20 Display must recognize two cases:=20
        1. ofc =3D=3D '\0': send the contents to output with = nothing between=20 them=20
        2. ofc !=3D '\0': send the contents to output with = ofc=20 separating them
Thus, for example, = S.Display(std::cout)=20 would send the contents of S to standard output.=20
    8. The output operator should be overloaded as follows:
template < typename T , size_t N >
std::ostream& operator << (std::ostream& os, const =
TStack<T,N>& S)
{
  S.Display (os, '\0');
  return os;
}

template < typename T >
std::ostream& operator << (std::ostream& os, const =
TQueue<T>& S)
{
  S.Display (os, '\0');
  return os;
}
The overload of operator <<() should be placed in = your=20 stack/queue header file immediately following the class definition. =
    9. The classes TStack amd TQueue should be in the=20 fsu namespace.
    10. The files tstack.h and tqueue.h should be = protected=20 against multiple reads using the #ifndef ... #define ... = #endif=20 mechanism.
    11. The test client programs ftstack.cpp and = ftqueue.cpp=20 should adequately test the functionality of stack and queue, = respectively,=20 including the output operator. It is your responsibility to create = these test=20 programs and to use them for actual testing of your stack and queue = data=20 structures.
Hints
    • Your test clients can be modelled on the harness = fbitvect.cpp=20 distributed as part of a previous assignment.
    • It is recommended that you carry the stack portion of the project = through=20 to completion, including implementation and testing, before starting = on the=20 queue portion. The implementation plan for TStack uses design = and=20 methodology that you already have experience with. The implementation = plan for=20 TQueue uses design and methodology that is very different and = new.=20
    • Keep in mind that the implementations of class template methods are = in=20 themselves template functions. For example, the implementation of the=20 TStack method Pop() would look something like this: =
template < typename T , size_t N >
T TStack<T,N>::Pop()
{
  // yada dada
  return ??;
}
and the TQueue method Pop() would = look=20 something like this:=20
template < typename T >
T TQueue<T>::Pop()
{
  // yada dada
  return ??;
}
    • We will test your implementations using (1) your supplied test = clients, (2)=20 in2post, and (3) test clients of our own design.
    • There are two versions of TStack::Top() and=20 TQueue::Front(). These are distunguished by "const"=20 modifiers for one of the versions. The implementation code is = identical for=20 each version. The main point is that "Top()" can be called on = a=20 constant stack, but the returned reference may not be used to modify = the top=20 element. This nuance will be tested in our assessment. You can test it = with=20 two functions such as:
char ShowTop(const fsu::TStack<char>& s)
{
  return s.Top();
}

void ChangeTop(fsu::TStack<char>& s, char newTop)
{
  s.Top() =3D newTop;
}
Note that ShowTop has a const reference to a = stack, so=20 would be able to call the const version of Top() but not the=20 non-const version, but that suffices. ChangeTop would need to = call=20 the non-const version in order to change the value at the top of the = stack. A=20 simple test named "constTest.cpp" is posted in the = distribution=20 directory.