# CHAPTER 9: STACKS AND QUEUES

In this chapter, we take a look at two data structures, stacks and queues, that can be created from the fundamental array and linked-list structures. In Chapters 1 and 3, you saw some examples of stacks. Here we will design stacks as concrete data types, with an eye on efficiency. Queues will be implemented with the same design philosophy. The idea is to define stack and queue classes that are readily usable in your own applications--with minimum overhead.

Stacks and queues are related data structures. Both are sequences of elements with restricted access. A stack is known as a last-in, first-out (LIFO) structure, where access to the elements takes place at one end of the sequence (called the top), using the operations push and pop. Figure 9.1 shows an example of a stack. A queue is a sequence where elements are inserted at one end (the tail), and extracted from the other end (the head). Queues work in a first-in, first out (FIFO) manner, as illustrated in Figure 9.2. Lines of cars at a traffic light, lines at the post office, and computer jobs waiting to be printed are all conceptual examples of queues.

#### Figure 9.3 A Double-ended queue.

A priority queue is another variation of a queue. Here, the elements are ordered by priorities that have been assigned to them, rather than by the order in which the elements are inserted. Figure 9.4 shows an example of a prioriity queue, with numbers representing the priority order. Notice that the sequence of elements are in descending order. You'll see priority queues implemented in Chapters 12. See also the companion volume [Flamig 93].

We'll now take a detailed look at stacks and queues, starting with fixed-size stacks.

## FIXED-SIZE STACKS

Should the stack be statically or dynamically allocated?

How should you keep track of the top of the stack and the bounds of the stack?

When should the stack elements be constructed and destructed?

The first issue can be handled quite easily. As we did for the arrays defined in Chapter 4, a base class can be defined that purposely avoids specifying how the stack elements are allocated. Then, we can derive specific classes for both statically and dynamically allocated stacks.

You can take two basic approaches to resolve the second issue (keeping track of the top and bounds of the stack). One approach is to use an index to indicate which element is at the top of the stack. When doing pushing and popping, this index can be checked with the bounds of the stack. This is the approach used in most books to implement array-based stacks. (Indeed, we used this approach in Chapters 3.) However, an index is not the best way to push and pop stack elements because subscripting involves multiplication and addition. A more efficient approach is to use pointers, both to reference the top of the stack and to mark the bounds of the stack.

#### Figure 9.4 A priority queue.

Why bother with the in-place construction method? It's intuitively appealing and, in some cases, more correct to construct elements only when they are used. For example, constructed elements might use other resources (such as open file handles), allocate memory buffers, and so on. By deferring construction until the element is actually used, and destroying the element after it's no longer needed, you can ensure that the resources used by the element are acquired and freed in a timely fashion.

The types of constructors available can help you determine whether to use in-place construction. It may not make sense for the element type to have a default constructor (perhaps there is no sensible notion of a "null" object of that type). In this case, in-place construction is the best choice. Of course, for in-place construction to be used, the type must have a copy constructor, something that may not always be desirable either.

## A Base Class for Array-Based Stacks

`template<class TYPE>`

`class ArrStk {`

`protected:`

`TYPE *start, *finish, *nxt;`

`unsigned dimlen;`

`void Setup(TYPE *m, unsigned n);`

`ArrStk(const ArrStk<TYPE> &);`

`public:`

`ArrStk(TYPE *m, unsigned n);`

`virtual ~ArrStk( );`

`void operator=(const ArrStk<TYPE> &s);`

`void Copy(const ArrStk<TYPE> &s);`

`int Push(const TYPE &x);`

`int Pop(TYPE &x);`

`int Pop( );`

`void FastPush(const TYPE &x);`

`void FastPop(TYPE &x);`

`TYPE *Top( );`

`const TYPE *Top( ) const;`

`TYPE *History(unsigned n);`

`const TYPE *History(unsigned n) const;`

`void Rewind(unsigned n=0);`

`int IsFull( ) const;`

`int IsEmpty( ) const;`

`unsigned Size( ) const;`

`};`

Complete code for the ArrStk class is given on disk in the files arrstk.h, arrstk.mth, and placenew.h. Through the use of defined macros, the code on disk can handle both the in-place copy-construction method and the conventional default-construction method. In this book, we show only the in-place construction method.

`template<class TYPE>`

`ArrStk<TYPE>::ArrStk(TYPE *m, unsigned n)`

`// Sets up a stack with n already-allocated elements`

`// pointed to by m`

`{`

`Setup(m, n);`

`}`

`template<class TYPE>`

`void ArrStk<TYPE>::Setup(TYPE *m, unsigned n)`

`{`

`start = m;`

`nxt = start;`

`if (start) { // Was memory actually allocated?`

`finish = start + n;`

`dimlen = n;`

`}`

`else {`

`finish = start;`

`dimlen = 0;`

`}`

`}`

`template<class TYPE>`

`int ArrStk<TYPE>::Push(const TYPE &x)`

`// Pushes a copy of x onto the stack unless`

`// stack is full. Returns 1 if not full;returns 0 otherwise.`

`{`

`if (!IsFull( )) {`

`new(nxt++) TYPE(x); // In-place copy construction`

`return 1;`

`}`

`else return 0;`

`}`

The Pop( ) function works in reverse, first decrementing the nxt pointer and then invoking an explicit destructor call. Figure 9.6(b) illustrates the popping process.

`template<class TYPE>`

`int ArrStk<TYPE>::Pop(TYPE &x)`

`// Pops the top element from the stack, returning`

`// a copy of it in x, unless stack is empty. Returns 1`

`// if stack wasn't empty before the pop; otherwise, returns 0.`

`{`

`if (!IsEmpty( )) {`

`x = *(--nxt);         // Make a copy`

`nxt->TYPE::~TYPE( );  // Explicit destruction`

`return 1;`

`}`

`else return 0;`

`}`

#### (b) Popping

`template<class TYPE>`

`void ArrStk<TYPE>::FastPush(const TYPE &x)`

`// For fastest, but unsafest pushes.`

`{`

`new(nxt++) TYPE(x); // In-place copy construction`

`}`

`template<class TYPE>`

`void ArrStk<TYPE>::FastPop(TYPE &x)`

`// For fastest, but unsafest pops.`

`{`

`x = *(--nxt);         // Make a copy`

`nxt->TYPE::~TYPE( );  // Explicit destruction`

`}`

It's interesting to compare in-place construction and explicit destruction with the conventional method, where all elements remain constructed during the stack's life. Here's how FastPush( ) and FastPop( ) would be coded for the latter:

`template<class TYPE>`

`void ArrStk<TYPE>::FastPush(const TYPE &x)`

`// If in-place construction isn't being used`

`// (assumes element already constructed)`

`{`

`x = *nxt++;`

`}`

`template<class TYPE>`

`void ArrStk<TYPE>::FastPop(TYPE &x)`

`// If in-place construction isn't being used`

`// (assumes element to remain constructed)`

`{`

`x = *(--nxt);`

`}`

You can see that the in-place construction used during a push is replaced by an assignment and that the code for a pop is the same as before, except no destructor call is made. For many element types, an assignment and a copy construction involve roughly the same amount of work. Thus, the push operation will take basically the same amount of time regardless of the method used. For pop operations, more work is being done in the extra destructor call for the in-place construction method. The data type being stored determines whether this is a problem or whether the reverse situation (not doing a destructor call) is a problem.

The in-place construction method provides the most rigorous design and is probably worth using, even if there is a slight performance penalty. Of course, for built-in types, this is a moot point since copy construction reduces to an assignment, and the destructor becomes a no-op.

`template<class TYPE>`

`void ArrStk<TYPE>::Rewind(unsigned n)`

`{`

`if (n == 0) n = dimlen; // Ensures all elements popped`

`// Explicit destructor called for each element popped`

`while(n-- && nxt != start) (--nxt)->TYPE::~TYPE();`

`}`

Unlike Pop( ), the Rewind( ) function doesn't copy and pass back the data being popped from the stack. The data is simply discarded and destroyed. The Rewind( ) function can be used to clear the stack by unpopping all the elements. By convention, passing a number 0 to Rewind( ) (the default) results in the stack being cleared.

`template<class TYPE>`

`TYPE *ArrStk<TYPE>::History(unsigned n)`

`{`

`if (IsEmpty( )) return 0;`

`TYPE *p = nxt-l;`

`while(1) {`

`if (n-- == 0) return p;     // Found the element`

`if (p-- == start) return 0; // Out of range`

`}`

`}`

`template<class TYPE>`

`TYPE *ArrStk<TYPE>::Top()`

`{`

`return IsEmpty() ? 0 : (nxt-1);`

`}`

`template<class TYPE>`

`void ArrStk<TYPE>::operator=(const ArrStk<TYPE> &s)`

`// Traps assignment to self`

`{`

`if (this != &s) Copy(s);`

`}`

`template<class TYPE>`

`void ArrStk<TYPE>::Copy(const ArrStk<TYPE> &s)`

`// Clears the stack, and then copies the elements`

`// of s onto the stack. Note that if s.dimlen >`

`// dimlen, not all elements will be copied.`

`{`

`Rewind();`

`TYPE *t = s.start;`

`unsigned n = dimlen;`

`// Elements copied via in-place copy construction`

`while (n- && t != s.nxt) new(nxt++) TYPE(*t++);`

`}`

The Copy( ) function doesn't change the dimensioned length of the stack and, for that reason, a truncation may result during the copy.

You'll notice that a copy constructor is defined for ArrStk, but it is placed in the private section of the class. The constructor body (not shown) is actually empty. This approach prevents the user from trying to create a stack via copy construction. As defined, the ArrStk class is not responsible for allocating the stack elements, so it can't allocate a new stack to hold a copy of another stack. Likewise, a virtual destructor is defined in ArrStk, but it does nothing. It's up to the derived classes to handle the de-allocation of the stack elements.

The remaining ArrStk functions are those that determine the maximum size of the stack and whether the stack is empty or full:

`template<class TYPE>`

`unsigned ArrStk<TYPE>::Size( ) const`

`{`

`return dimlen;`

`}`

`template<class TYPE>`

`int ArrStk<TYPE>::IsEmpty( ) const`

`{`

`return nxt == start;`

`}`

`template<class TYPE>`

`int ArrStk<TYPE> : : IsFull ( ) const`

`{`

`return nxt == finish;`

`}`

## Statically Allocated Stacks

`template<class TYPE, unsigned SIZE>`

`class SarrStk : public ArrStk<TYPE> {`

`protected:`

`char elem[sizeof (TYPE)*SIZE]; // Notice the char type!`

`public:`

`SarrStk();`

`SarrStk (const ArrStk<TYPE> &s);`

`SarrStk (const SarrStk<TYPE, SIZE> &s);`

`virtual ~SarrStk ();`

`void operator=(const ArrStk<TYPE> &s);`

`} ;`

The SarrStk class uses the same strategy that was used for the statically allocated, variable-length arrays in Chapter 4. The stack elements are allocated and de-allocated as an array of characters. This approach defers the construction of the elements until they are actually used, and prevents them from being destroyed twice when the stack itself is destroyed. Here is one of the constructors, and the destructor, to illustrate this technique. In the destructor, the stack must be rewound so that we can call the destructors for all elements in use:

`template<class TYPE, unsigned SIZE>`

`SarrStk<TYPE, SIZE>: :SarrStk()`

`: ArrStk<TYPE>((TYPE *) elem, SIZE)`

`{`

`// Nothing else to do`

`}`

`template<class TYPE, unsigned SIZE>`

`SarrStk<TYPE, SIZE>: :~SarrStk()`

`{`

`Rewind();`

`}`

Complete code for the SarrStk class is given on disk in the file sarrstk.h. A test program tstsastk.cpp is also provided.

## Dynamically Allocated Stacks

`template<class TYPE>`

`class DarrStk : public ArrStk<TYPE> {`

`public:`

`DarrStk(unsigned n);`

`DarrStk(const ArrStk<TYPE> &s);`

`DarrStk(const DarrStk<TYPE> &s);`

`virtual ~DarrStk();`

`void operator=(const ArrStk<TYPE> &s);`

`};`

`template<class TYPE>`

`DarrStk<TYPE>: :DarrStk(unsigned n)`

`// Elements are allocated as an array of characters`

`// to defer their construction until needed`

`: ArrStk<TYPE>( (TYPE *)new char[sizeof(TYPE)*n], n)`

`{`

`// Nothing else to do`

`}`

`template<class TYPE>`

`DarrStk<TYPE>::~DarrStk()`

`{`

`Rewind();`

`// Elements are deleted as an array of characters,`

`// since that's how they were allocated`

`delete[] (char *)start;`

`}`

Complete code for the DarrStk class is given on disk in the file darrstk.h. The test program tstdastk.cpp is also provided.

## RESIZABLE STACKS

Fixed-size, array-based stacks provide the most efficient form of stack; however, it can be inconvenient to fix the size of the stack. A linked list is the obvious candidate to implement a resizable stack. We provided examples of this in Chapter 3. Unfortunately, when we use a linked list, a new node must be allocated from the heap with every push, and a node must be de-allocated with every pop. For some heap-implementations, this can be a time-consuming process. In Chapter 8, we demonstrated one way around this problem: implement an auxiliary list to cache nodes that would otherwise be freed.

A resizable array, as implemented in Chapter 4, provides another alternative. However, this approach presents a problem: each time the array grows beyond its allocated bounds, it has to be copied into a new location that has more room.

## Stacks of Stacks

You can implement a stack-of-stacks using the DarrStk template, with the element type being the DarrStk type itself. In the following example, we'll declare such a stack, with room to hold mxstks substacks:

`DarrStk< DarrStk<TYPE> > stkostk (mxstks);`

When stkostk is first allocated, the individual substacks remain unconstructed. As a result, the only space initially occupied by stkostk is the space for the instance variables of DarrStk (start, finish, nxt, and dimlen) multiplied mxstks times. Substacks are constructed only when elements are pushed onto the stack. Here's how an element x of type TYPE can be pushed onto and popped from the stack:

`// Push function:`

`if (!stkostk.IsFull()) {`

`if (stkostk.IsEmpty() || stkostk.Top()->IsFull()) {`

`stkostk.Push(DarrStk<TYPE>(blksize));`

`}`

`return stkostk.Top() ->Push(x);`

`}`

`else return 0 ;`

`// Pop function:`

`if (!stkostk.IsEmpty()) {`

`if (stkostk.Top()->IsEmpty()) {`

`stkostk.Rewind(1);`

`if (stkostk.IsEmpty()) return 0;`

`}`

`return stkostk.Top( )->Pop(x);`

`}`

`else return 0;`

A working example of a stack-of-stacks is given on disk in the file stkostk.cpp.

## The RarrStk Class

`template<class TYPE>`

`class RarrStk {`

`protected:`

`TYPE **stkostk;             // Stack-of-stacks pointers`

`TYPE *nxt, *start, *finish; // Current stack variables`

`unsigned maxnelems, stksize, nxtstk, maxstks;`

`int Setup(unsigned nb);`

`int PushStk();`

`void PopStk(unsigned b);`

`void Dealloc();`

`public:`

`RarrStk(unsigned stksz, unsigned mxstks=1);`

`RarrStk(const RarrStk<TYPE> &s);`

`~RarrStk();`

`void operator=(const RarrStk<TYPE> &s);`

`int Copy(const RarrStk<TYPE> &s);`

`int Push(const TYPE &x);`

`int Pop(TYPE &x);`

`int Pop();`

`TYPE *Top();`

`const TYPE *Top() const;`

`TYPE *History (unsigned n);`

`const TYPE *History(unsigned n) const;`

`void Rewind(unsigned n = 0);`

`int IsFull() const;`

`int IsEmpty() const;`

`unsigned Size() const;`

`};`

Complete code for the RarrStk class is given in the files rarrstk.h and rarrstk.mth. A test program is provided in the file tstrastk.cpp.

`template<class TYPE>`

`RarrStk<TYPE>::RarrStk(unsigned stksz, unsigned mxstks)`

`{`

`stksize = stksz;`

`Setup(mxstks);`

`}`

`template<class TYPE>`

`int RarrStk<TYPE>::Setup(unsigned ns)`

`{`

`nxtstk = 0; nxt = 0; start = 0; finish = 0;`

`stkostk = new TYPE *[ns]; // Up to ns sub-stacks`

`if (stkostk) {`

`maxstks = ns;`

`while(ns) stkostk[-ns] = 0;`

`}`

`else maxstks = 0;`

`maxnelems = stksize * maxstks;`

`return maxstks > 0;`

`}`

#### Figure 9.7 A partially filled RarrStk object.

When calling the constructor, you specify the size of each substack and the number of substacks that you wish to allow. Note that a RarrStk object does have a maximum size (equal to stksixe * maxstks), but unlike an ArrStk object, this size doesn't affect the initial amount of memory reserved. Initially, RarrStk only requires enough room to store the stkostk array of pointers.

Elements are pushed on the stack in the same way that we used previously, with one exception: if the current substack is full, a new substack is started. Figure 9.8 illustrates this process. The following Push( ) and PushStk( ) routines show how the pushing is done. You'll notice that in-place construction is used for the new element:

`template<class TYPE>`

`int RarrStk<TYPE>::Push(const TYPE &x)`

`}`

`if (nxt == finish) {           // Need another stack`

`if (!PushStk()) return 0;  // Couldn't allocate`

`}`

`new(nxt++) TYPE(x);  // In-place copy construction`

`return 1;            // Success`

`}`

`template<class TYPE>`

`int RarrStk<TYPE>::PushStk( )`

`// Ensures room has been allocated for the next highest`

`// stack (ie: stk # nxtstk.) Returns 1 if successful;`

`// returns 0 if unable to allocate.`

`{`

`if (nxtstk == maxstks) return 0: // Table full`

`TYPE *p = stkostk[nxtstk];`

`if (p == 0) { // Block not already allocated`

`p = (TYPE *)new char[stksize*sizeof(TYPE)];`

`stkostk[nxtstk] = p; // Record stack pointer`

`}`

`// else stack still allocated from before`

`if (p) { // We have stack allocated`

`nxt = start = p;`

`finish = p + stksize;`

`nxtstk++;`

`return 1;`

`}`

`else { // Allocation error, so leave everything alone`

`return 0;`

`}`

`}`

The PushStk( ) routine--responsible for ensuring that a new substack gets allocated--is somewhat tricky. First, the substack may already be allocated (more on this later), which we determine by checking for a non-null pointer in stkostk. Second, since we're using in-place construction, the new substack is allocated as an array of characters to prevent the element constructors from being called prematurely. Note how the variable nxtstk keeps track of the next available location in stkostk, and how it's possible for stkostk to become completely full.

#### Figure 9.8 Pushing onto a RarrStk object.

`template<class TYPE>`

`int RarrStk<TYPE>::Pop(TYPE &x)`

`// Pops the top element from the stack, returning`

`// a copy of it in x. Returns 1 if stack wasn't empty`

`// before push; otherwise, returns 0. If stack was empty, the`

`// data in x will be untouched.`

`{`

`if (nxt == start) {`

`// Pop next higher stack if this has not already been done`

`PopStk(nxtstk);`

`// Return if stack is empty, but note that there may`

`// still be a stack allocated (when nxtstk = 1)`

`if (nxtstk <= 1) return 0;`

`// Otherwise, we must move to end of lower stack`

`-nxtstk; // nxtstk guaranteed >= 1 after decrement`

`start = stkostk[nxtstk-1];`

`finish = start + stksize;`

`nxt = finish - 1;`

`}`

`else -nxt;`

`x = *nxt;`

`nxt->TYPE::~TYPE( );`

`return 1;`

`}`

`template<class TYPE>`

`void RarrStk<TYPE>::PopStk(unsigned b)`

`// De-allocates stack b if not already de-allocated,`

`// destructing elements along the way if INPLACECONST`

`// isn't true. Sets pointer in stack table`

`// to null. Does nothing if b is out of range.`

`{`

`if (b >= maxstks) return; //  b is out of range`

`if (stkostk[b] == 0) return;`

`delete[] (char *)(stkostk[b]);`

`stkostk[b] = 0;`

`}`

Stacks based on the RarrStk class are quite efficient, but they are slightly slower than those based on ArrStk--due to the need to allocate and de-allocate sub-stacks. This problem can be alleviated by increasing the size of the blocks, and thus reducing the frequency of substack allocations. Note that RarrStk objects are significantly faster than a linked list approach. The RarrStk objects also occupy less space, since each element doesn't need an extra link pointer. The only disadvantage is a slight increase in the code required (which could be magnified if many classes are instantiated from the template).

#### Figure 9.9 Delayed de-allocation of a substack.

To allow you to compare RarrStk objects with linked-list based stacks, we've provided the following additional files on disk: liststk.h, liststk.mth, tstlstk.cpp, and stktimer.cpp. The latter program tests the runtime efficiency of the two approaches.

## LIST-BASED QUEUES

1. Implement a linked-list queue class from scratch. This is the most direct method. However, with this approach we must duplicate a lot of list functionality that could be reused for other lists.

2. Use the Slist class of Chapter 8 as is, without creating a special queue version. We can use functions like AddToBack( ) and DelFront( ) to support the queue operations. However, all the other list operations are available as well, such as DelNext( ), which violate restricted access to the ends of the queue. Whether this is a problem depends on how strictly you wish to follow the definition for a queue.

For this book, we've chosen the fourth method, since it is perhaps the best engineering tradeoff. However, the method that works best for you might depend on a lot of factors; don't hesitate to implement queues using your own methods.

`template<class TYPE>`

`class ListQ : public Slistb {`

`protected:`

`virtual Snode<TYPE> *AllocNode(const TYPE &x);`

`virtual Snodeb *DupNode(const Snodeb *n);`

`virtual void FreeNode(Snodeb *n);`

`public:`

`ListQ();`

`ListQ(const ListQ<TYPE> &s);`

`~ListQ();`

`void operator=(const ListQ<TYPE> &s);`

`int Extract(TYPE &x);`

`int Extract();`

`int Insert(const TYPE &x);`

`TYPE *Head();`

`const TYPE *Head() const;`

`int IsFull() const;`

`};`

Complete code for the ListQ class is given on disk in the files listq.h, listq.mth, and snode.h. A test program is given in tstlq.cpp.

The ListQ class is very similar to the Slist class, but has fewer functions. For instance, we chose not to support queue concatenations, even though this might be useful in some cases. As was true with the Slist class, ListQ allocates nodes on the heap. We could, of course, use the free-list technique for node caching or use array-based allocation.

The most important functions of ListQ are Insert( ) and Extract( ), which implement the basic queue operations:

`template<class TYPE>`

`int ListQ<TYPE>::Insert(const TYPE &x)`

`// Creates a new node having a copy of x for its data`

`// and puts in on the back of the queue. Returns 1`

`// if allocation successful; otherwise, returns 0.`

`{`

`Snode<TYPE> *p = AllocNode(x);`

`if (p == 0) return 0;`

`AttachToBack(p);`

`return 1;`

`}`

`template<class TYPE>`

`int ListQ<TYPE>::Extract(TYPE &x)`

`// Gets the data from the front node of the queue and`

`// copies it into x. If queue is empty, x is left`

`// untouched and a 0 is returned; otherwise, returns a 1.`

`{`

`Snode<TYPE> *p = (Snode<TYPE> *)RmvFront( );`

`if (p == 0) return 0;`

`x = p->info;`

`FreeNode(p);`

`return 1;`

`}`

`template<class TYPE>`

`TYPE *ListQ<TYPE>::Head( )`

`// Returns the data contained in the head node of the queue,`

`// or a null pointer if the queue is empty`

`{`

`return IsEmpty() ? 0 : &(((Snode<TYPE> *)Front())->info);`

`}`

Figure 9.10 illustrates the process of adding and removing elements from a ListQ object.

## LIST-BASED DEQUES

#### Figure 9.10 Using a ListQ object.

You can either choose to accept this inefficiency or use a doubly-linked list. Of course, a doubly-linked list has its own inefficiency, costing an extra pointer per node. As always, you are faced with the classic speed versus space tradeoff. Here, sacrificing space for speed is probably the better choice. The space required by a queue is rarely an issue. However, the speed to remove an element might be. (If space is an issue, an array-based queue is a better approach, as you'll see later on.)

`template<class TYPE>`

`class ListDQ : public Dlistb {`

`protected:`

`virtual Dnode<TYPE> *AllocNode (const TYPE &x);`

`virtual Dnodeb *DupNode(const Dnodeb *n);`

`virtual void FreeNode(Dnodeb *n);`

`public:`

`ListDQ();`

`ListDQ(const ListDQ<TYPE> &s);`

`~ListDQ();`

`void operator=(const ListDQ<TYPE> &s);`

`int ExtractHead(TYPE &x);`

`int ExtractTail(TYPE &x);`

`int InsertHead(const TYPE &x);`

`int InsertTail(const TYPE &x);`

`TYPE *Head();`

`const TYPE *Head() const;`

`TYPE *Tail();`

`const TYPE *Tail() const;`

`int IsFull() const;`

`};`

Complete code for the ListDQ class is given in the files listdq.h, listdq.mth, and dnode.h. A test program is provided in the file tstldq.cpp.

`template<class TYPE>`

`int ListDQ<TYPE>::InsertHead(const TYPE &x)`

`{`

`Dnode<TYPE> *p = AllocNode(x);`

`if (p == 0) return 0;`

`AttachToFront(p);`

`return 1;`

`}`

`template<class TYPE>`

`int ListDQ<TYPE>::InsertTail(const TYPE &x)`

`{`

`Dnode<TYPE> *p = AllocNode(x);`

`if (p == 0) return 0;`

`AttachToBack(p);`

`return 1;`

`}`

`template<class TYPE>`

`int ListDQ<TYPE>::ExtractHead(TYPE &x)`

`{`

`Dnode<TYPE> *p = (Dnode<TYPE> *)RmvFront( );`

`if (p == 0) return 0;`

`x = p->info;`

`FreeNode(p);`

`return 1;`

`}`

`template<class TYPE>`

`int ListDQ<TYPE>::ExtractTail(TYPE &x)`

`{`

`Dnode<TYPE> *p = (Dnode<TYPE> *)RmvBack( );`

`if (p == 0) return 0;`

`x = p->info;`

`FreeNode(p);`

`return 1;`

`}`

## ARRAY-BASED QUEUES

#### Figure 9.11 An inefficient array-based queue.

The chasing pointer technique does present some problems. As elements are extracted, the storage space at the beginning of the array is discarded and never reused. Also, the head and tail pointers are always incremented (but never decremented). Thus, even if the number of extractions equals the number of insertions, the array eventually runs out of space.

To solve these problems, we can use a circular array, also called a ring buffer. In such an array, the end wraps around to the beginning. Circular arrays don't physically exist. Instead, they are simulated by using normal linear arrays, where all pointers or indexes scanning the array are reset to the starting element when the ending element has been passed. Figure 9.13 illustrates this wraparound effect.

## The ArrQ Class

Pointers are used to represent the head and tail of the queue, and also for the actual bounds of the underlying array. This is more efficient than using indexes, since we can avoid the multiplication needed by subscripting.

In-place construction is used when elements are added and explicit destruction is used when elements are removed. This approach leads to a more rigorous and robust design.

The class is a concrete data type implemented as a template, with the appropriate constructors, destructor, and overloaded assignment operator.

#### Figure 9.13 A circular array with wrapround pointers.

Here is the ArrQ class definition:

`template<class TYPE>`

`class ArrQ {`

`protected:`

`TYPE *st,   // Pointer to start element`

`*fn,   // Pointer to finish element`

`*hd,   // Pointer to head element in the queue`

`*nx;   // Pointer to next available element`

`int isfull; //  Flag to indicate a full queue`

`unsigned dimlen;  // Maximum number of elements`

`void Setup(TYPE *m, unsigned n);`

`ArrQ(const ArrQ<TYPE> &); // To disallow copy constructing`

`TYPE *Inc(TYPE *x) const;`

`TYPE *Dec(TYPE *x) const;`

`public:`

`ArrQ(TYPE *m, unsigned n);`

`virtual ~ArrQ();`

`void operator=(const ArrQ<TYPE> &s);`

`int Copy(const ArrQ<TYPE> &s);`

`void Clear();`

`int Extract(TYPE &x);`

`int Extract();`

`int Insert(const TYPE &x);`

`TYPE *Head();`

`const TYPE *Head() const;`

`int IsEmpty() const;`

`int IsFull() const;`

`unsigned Size() const;`

`};`

Complete code for the ArrQ class is given on disk in the files arrq.h and arrq.mth. Static and dynamic derived classes are given in the files sarrq.h and darrq.h. Test programs can be found in the files tstsaq.cpp and tstdaq.cpp.

`template<class TYPE>`

`ArrQ<TYPE>::ArrQ(TYPE *m, unsigned n)`

`// Constructs a new queue with a maximum of n elements`

`// stored at location m, assumed to be already allocated`

`{`

`Setup(m, n);`

`}`

`template<class TYPE>`

`void ArrQ<TYPE>::Setup(TYPE *m, unsigned n)`

`{`

`st = m;`

`if (st && n) { // Array isn't null`

`fn = st+n-1;`

`dimlen = n;`

`isfull = 0;`

`}`

`else { // A null array, which is always 'full'`

`fn = st;`

`dimlen = 0;`

`isfull = 1;`

`}`

`hd = st;`

`nx = st;`

`}`

Figure 9.14(a) shows the configuration of an empty queue as created by Setup( ). Note how the nx and hd pointers are equal at this stage. The condition nx==hd is one way to test for an empty queue. However, this condition also occurs when the queue is full, as illustrated by Figure 9.14(b).

#### (B) Full

`template<class TYPE>`

`int ArrQ<TYPE>::IsEmpty( ) const`

`{`

`return hd == nx && !isfull;`

`}`

`template<class TYPE>`

`int ArrQ<TYPE>::IsFull( ) const`

`{`

`return isfull;`

`}`

`template<class TYPE>`

`int ArrQ<TYPE>::Insert(const TYPE &x)`

`// Copies x into the next available element at the end`

`// of the queue. If queue is full, nothing happens.`

`{`

`if (IsFull( )) return 0;`

`new(nx) TYPE(x);`

`nx = Inc(nx);`

`if (nx == hd) isfull = 1; // We just went full`

`return 1;`

`}`

`template<class TYPE>`

`int ArrQ<TYPE>::Extract(TYPE &x)`

`// Gets the data from the head element and stores a copy of`

`// it in x. Removes and possibly destroys the head element.`

`// If queue is empty, x is left untouched and a`

`// 0 is returned; otherwise, a 1 is returned.`

`{`

`if (IsEmpty()) return 0;`

`x = *hd;`

`hd->TYPE::~TYPE();`

`hd = Inc(hd); // We have a new head`

`isfull = 0;   // And we certainly can't be full anymore`

`return 1;`

`}`

`template<class TYPE>`

`TYPE *ArrQ<TYPE>::Inc(TYPE *x) const`

`// Increments a pointer and wraps around to`

`// the start if necessary`

`{`

`return (x == fn) ? st : x+1;`

`}`

`template<class TYPE>`

`TYPE *ArrQ<TYPE>::Dec(TYPE *x) const`

`// Decrements a pointer, wrapping around to`

`// the end if necessary`

`{`

`return (x == st) ? fn : x-1;`

`}`

## Array-Based Staques

Complete code for an array-based staque class is given on disk in the files arrsq.h and arrsq.mth. Static and dynamic versions, SarrSQ and DarrSQ, are provided in the files sarrsq.h and darrsq.h. Two test programs are provided in tstsasq.cpp and tstdasq.cpp.

## The ArrDQ Class

`template<class TYPE>`

`class ArrDQ : public ArrQ<TYPE> {`

`protected:`

`ArrDQ(const ArrDQ<TYPE> &s);`

`public:`

`ArrDQ(TYPE *m, unsigned n);`

`void operator=(const ArrQ<TYPE> &s);`

`int ExtractHead(TYPE &x);`

`int ExtractTail(TYPE &x);`

`int InsertHead(const TYPE &x);`

`int InsertTail(const TYPE &x);`

`TYPE *Tail( );`

`const TYPE *Tail( ) const;`

`};`

Complete code for the ArrDQ class is given on disk in the files arrdq.h and arrdq.mth. Static and dynamic classes, SarrDQ and DarrDQ, are given in the files sarrdq.h and darrdq.h. Test programs are provided in the files tstsadq.cpp and tstdadq.cpp.

`template<class TYPE>`

`int ArrDQ<TYPE>::InsertHead(const TYPE &x)`

`// Puts a new element at the front of the queue, holding`

`// a copy of x`

`{`

`if (IsFull( )) return 0;`

`hd = Dec(hd);`

`new(hd) TYPE(x);`

`if (nx == hd) isfull = 1;`

`return 1;`

`}`

`template<class TYPE>`

`int ArrDQ<TYPE>::InsertTail(const TYPE &x)`

`// Puts a new element at the end of the queue, holding a`

`// copy of x`

`{`

`return ArraQ<TYPE>::Insert(x);`

`}`

`template<class TYPE>`

`int ArrDQ<TYPE>::ExtractHead(TYPE &x)`

`// Copies the data of the front element into x and`

`// removes the element from the queue`

`{`

`return ArrQ<TYPE>::Extract(x);`

`}`

`template<class TYPE>`

`int ArrDQ<TYPE>::ExtractTail(TYPE &x)`

`// Copies the data of the rear element into x and`

`// removes the element from the queue`

`{`

`if (IsEmpty( )) return 0;`

`nx = Dec(nx);`

`x = *nx;`

`nx->TYPE::~TYPE( );`

`isfull = 0;`

`return 1;`

`}`

Note that we could have derived the ArrDQ class from the ArrSQ class, since we would only need to add the function to remove elements from the end of the queue. We chose not to do this because the chain of template-based derivations (ArrQ to ArrSQ to ArrDQ to SarrDQ and DarrDQ) starts to get a little unwieldy. The derivation of ArrDQ directly from ArrQ eliminates one class from this chain.

## HETEROGENOUS STACKS AND QUEUES

The discussion so far has implicitly assumed that the stacks and queues store only one kind of object, and are thus homogenous. However, you will probably have situations where it is useful to store different types of objects. Any of the techniques given earlier in Chapters 5 and 8 for creating heterogenous arrays and linked-lists could also be used for stacks and queues. As always, you can accomplish this by storing indirect pointers to objects, perhaps using reference-counted smart pointers to provide the safest designs.

## SUMMARY

In this chapter, you've seen how to efficiently implement stacks and queues by using two opposing data structures: arrays and linked lists. Both forms offer advantages. Linked lists allow more flexibility for variable stack and queue lengths, while arrays offer more compact representations when a fixed size is acceptable. The RarrStk class provides a very efficient implementation of resizable stacks by using a stack-of-stacks. Note that resizable array-based queues could be implemented in a way similar to the RarrStk class, using a queue of queues. The details are somewhat messy, though, because the deferred allocation and deallocation of the subqueues must be handled in both directions.

Perhaps the most important design feature presented in this chapter is the use of in-place construction and explicit destruction of elements when they are added and removed from the stacks and queues. Most texts on C++ do not mention this technique, yet in-place construction does lead to a more robust design.