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.

It's possible to combine a stack and queue to arrive at another data structure, which we'll call a *staque*. (This terminology was invented by the author.) In a staque, the stack operations push and pop are defined, as well as the queue operations *insert* (into the tail) and *extract* (from the front.) Of course, the extract operation is identical to the pop operation.

By taking this approach one step further, we could also allow extraction from the tail. The result is known as a *double-ended queue*, or *deque*. Figure 9.3 shows an example of a deque.

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.

The most common type of stack is a fixed-size stack, implemented as an array of elements. When you define array-based stacks, you need to consider these three main design issues:

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.

You can also take two approaches to resolve the third issue (determining when to construct and deconstruct stack elements). The easiest approach is to construct the elements using default constructor calls when the stack is first built, and to destroy all the elements when the stack itself is destroyed. Indeed, that's the conventional way that C++ handles arrays. The second approach is to construct the stack elements individually during push operations, and to destroy elements one at a time during pop operations. This can be done using in-place copy constructor calls and explicit destructor calls--the same techniques we used for the variable-length arrays in Chapter 4.

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.

Using the preceding design principles, we'll now define a base class, *ArrStk*, which handles the basic operations of a fixed-sized array-based stack. The class assumes the stack elements are allocated elsewhere:

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;

};

The *ArrStk* constructor takes a pointer to the stack elements (assumed to be already allocated, but not constructed) and the number of elements allocated. The *Setup( )* function does all the work:

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;

}

}

The *Setup( )* function initializes the three pointers *start, nxt*, and *finish*, and the maximum stack size *dimlen*. The *start* and *finish* pointers mark the beginning and end of the stack, where *finish* actually points one element past the end. The *nxt* pointer references the next available stack element. The top of the stack--that is, the previous element pushed--can be found at *nxt-1*. When *nxt* equals *start*, the stack is empty. When *nxt* equals *finish*, the stack is full. Figure 9.5 shows the arrangement of an *ArrStk* object at various stages.

An element is pushed onto the stack by copy-constructing the data in place, at the location referenced by *nxt*, and then incrementing the *nxt* pointer, as given in the following *Push( )* function. Figure 9.6(a) illustrates the pushing process.

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;

}

Both *Push( )* and *Pop( )* check to make sure the bounds of the stack aren't violated. To optimize speed, you may want to forgo these checks--but only if this is warranted! The following *FastPush( )* and *FastPop( )* functions are provided to bypass the stack checks. These functions can be easily inlined:

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

}

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);

}

The *Rewind( )* function is related to *Pop( )*, and lets you unpop* n* elements off the stack:

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();

}

*History( )* is another related function, and lets you inspect the element *n* positions back into the stack:

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

}

}

In the strictest sense, *History( )* violates the rules of a stack. However, this function can be quite useful, when stacks are used in conjunction with tree-traversal algorithms. In the case of *n* = *0*, the top element of the stack is inspected. The *Top( )* function provides an efficient form for this special case:

template<class TYPE>

TYPE *ArrStk<TYPE>::Top()

{

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

}

To make *ArrStk* a concrete data type, we also provide an overloaded assignment operator to allow stacks to be copied. This operator function calls *Copy( )* to do most of the work:

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++);

}

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;

}

With the *ArrStk* class now defined, it's easy to derive a new class, *SarrStk*, that allocates the stack elements statically:

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.

The *DarrStk* class defines stacks that are dynamically allocated. As was done with the *SarrStk* class, we use a typecasting trick so that the stack elements can be allocated without being constructed at the same time. This next class definition, followed by one of the constructors and the destructor, illustrates the technique. This time, the destructor must not only rewind the stack, but also must delete the elements:

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;

}

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.

There is an array-based solution that's better than all of the alternatives just presented. The idea is based on working with multiple stacks. As a stack becomes full, a switch is made to a new stack. As a stack becomes empty, a switch is made back to a previously used stack. This type of resizable stack can be implemented using a *stack-of-stacks*. Initially, the stack-of-stacks is empty. When the first element is to be added, a new substack is allocated and a pointer to it is pushed onto the stack-of-stacks. When the first substack becomes full, another substack is allocated and its pointer is pushed onto the stack-of-stacks. As elements are removed and a substack becomes empty, the substack is popped from the stack-of-stacks.

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

// 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 nested template, stack-of-stacks approach works fine, but some stack operations--such as *Rewind( )* and *History( )*--are somewhat difficult to* *implement under this approach. For this reason, we'll implement a stack-of-stacks more directly, using the following* 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;

};

A *RarrStk* object is made up of an array of stack pointers called *stkostk* and one or more substacks. Each substack is allocated and de-allocated separately as needed, and *stkostk* keeps track of their locations. As is true with the *ArrStk* class, *RarrStk* uses the pointers *nxt*, *start*, and *finish*, but this time they point to elements in the current substack. When a switch is made to another substack, these pointers are modified accordingly. Figure 9.7 shows an example of a *RarrStk* object with two substacks allocated (but with room for four stacks).

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;

}

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.

Popping an element from the stack uses the reverse approach. If the current substack becomes empty when an element is popped off the stack, the sub-stack can be de-allocated. However, the substack shouldn't be de-allocated immediately. You should postpone the de-allocation to avoid the "thrashing" that can occur at the boundary of a substack. Consider what would happen if the first element of a substack is popped and a new element is then immediately pushed. If the substack were de-allocated as soon as it became empty, it would have to be immediately re-allocated when a new element is added. To avoid this, the following *Pop( )* function de-allocates a substack only when the one precedes it becomes empty. When a substack is ready to be freed, the *PopStk( )* function is called. Figure 9.9 illustrates the process.

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;

}

The *RarrStk* class contains a full complement of constructors, a destructor, and an overloaded assignment operator. As is the case with the *ArrStk* class, *RarrStk* includes functions like *IsEmpty( )*, *IsFull( )*, *History( )*, *Top( )*, *Rewind( )*, and so on. The details of these functions are given on disk.

We'll now focus on the implementations of queues. We'll begin by discussing list-based queues, since they are the easiest to implement. Next, we'll look at compact array-based implementations. Recall that, with a queue, elements are inserted at the rear of the queue and extracted from the front. A singly-linked list with a back pointer can handle these operations quite nicely. There are different methods we could use:

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.

3. *A queue-specific class template can be derived from the Slist class*. We can use private derivation, and thus control which list functions are available. By using inline functions, we can change the names of *AddToBack( )* and *DelFront( )* to more high-level names such as *Insert( )* and *Extract( )*. This approach gets messy because an extra template class, *Slist*, must be instantiated, plus we run into all sorts of protected-access problems. Of course, if you need the *Slist* class for some other part of your program, this approach may be best since you'll be reusing the *Slist* class.

4. *A queue-specific class template can be derived from the Slistb base class*. This represents a compromise of the other three approaches. By deriving from *Slistb*, we allow much of the code to be reused. Yet, because the derivation is direct, we'll have a simpler implementation than if we had used the *Slist* class.

We can derive a *ListQ* class from *Slistb*, whose purpose is to implement listbased queues:

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;

};

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;

}

The *Insert( )* and *Extract( )* functions use the *AttachToBack( )* and *RmvFront( )* functions of *Slistb*, as well as the virtual functions *FreeNode( )* and *AllocNode( ).*

Sometimes it's useful to peek at the front element in the queue without actually removing it. The *Head( )* function is used for that purpose:

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.

You can add stack-like operations to the *ListQ* class and derive a combination stack and queue (staque) class. Alternatively, you can derive the staque class from a stack class or, by using multiple inheritance, combine a stack and queue class. In the first case, the *Pop( )* function would be identical to *Exctract( )* and the *Push( )* operation could be implemented by making a call to the *AddToFront( )* function of *Slistb*. The details for this are given on disk.

Complete code for a list-based staque class, *ListSQ*, is given on disk in the files *listsq.h* and *listsq.mth.* This class is derived from a list-based stack class, *ListStk*, which is given in the files *liststk.h* and *liststk.mth.* A test program is provided in *tstlsq.cpp.*

Here, a singly-linked list with a back pointer isn't quite up to the job. The problem is that we can't efficiently remove the last node from the list, because we must scan the list from beginning to end to find the node immediately preceding the last one.

By using the doubly-linked list approach, we can implement a deque with the following *ListDQ* class, which is derived from *Dlistb*:

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;

};

The design of the *ListDQ* class is similar to *ListQ*, but splits the *Insert( )* and *Exctract( )* functions into four functions-*InsertHead( )*, *InsertTail( )*, *ExtractHead( )*, and *ExtractTail( )*:

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;

}

List-based queues are especially useful because you don't have to pre-allocate storage for the maximum size of the queue. However, if the queues you are using tend to be of some fixed size, then arrays offer more compact representations. Such array-based queues will be discussed next.

The simplest way to implement an array-based queue is to have the first element of the array be the head of the queue, and utilize a pointer to the tail of the queue. It's easy to insert an element into this type of queue. We simply increment the tail pointer to the next available slot. However, we run into a problem in extracting from the front of the queue, because doing so means all remaining elements of the array must be shifted up--a time-consuming process. Figure 9.11 illustrates this inefficiency.

An alternative is to use a *chasing pointer* technique. The idea is to add another pointer to the head of the queue. The head pointer is initialized to the start of the array. As elements are inserted, the tail pointer is incremented. As elements are extracted, the head pointer is incremented, chasing the tail pointer. With this strategy, both insertion and extraction are efficient, as illustrated in Figure 9.12.

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 isn't responsible for allocating memory for the queue. The derived classes *SarrQ* and *DarrQ* determine whether the memory is allocated statically or dynamically. These classes are similar to *SarrStk* and *DarrStk*.

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;

};

Four pointers are used to represent the queue. The variable *st* points to the starting element in the array, *fn* points to the last element in the array, *hd* points to the logical start of the queue, and *nx* points to the next element available for insertions. The tail of the queue can be found at location *nx-1*. The *ArrQ *constructor sets up these pointers by calling *Setup( )*.

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).

We can solve this ambiguity in two ways. Under one approach, we never let the array fill up entirely, holding the last remaining element in reserve. (The location of this element rotates through the array as the queue is accessed.) In this scheme, when *nx ==hd-1*, the queue is said to be full. Unfortunately, the reserved element represents wasted space, which can be costly if the array elements are large. Under the second approach, we maintain a flag (which we call *isfull*) that is set when the queue becomes full during an insertion and reset as elements are extracted. The following *IsEmpty( )* and *IsFull( )* functions show how the *isfull* flag resolves the empty/full ambiguity:

template<class TYPE>

int ArrQ<TYPE>::IsEmpty( ) const

{

return hd == nx && !isfull;

}

template<class TYPE>

int ArrQ<TYPE>::IsFull( ) const

{

return isfull;

}

By maintaining the *isfull* flag, we avoid wasting one of the array elements, but we do create some complications. Here are the *Insert( )* and *Extract( ) *functions, which illustrate how the *hd* and *nx* pointers are updated, and how the *isfull* flag is maintained:

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;

}

The functions *Inc( )* and *Dec( )* are used to conveniently wrap the pointers around when we reach the ends of the array:

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;

}

We can now derive a new class that adds stack-like operations to the *ArrQ* class, similar to the way used for list-based stacks. Such a class, *ArrSQ*, is given on disk.

A double-ended queue class is easy to derive from *ArrQ*, as the following *ArrDQ* class shows:

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;

};

The *Insert( )* and *Extract( )* functions of the *ArrQ* class are replaced by *InsertHead( )*, *InsertTail( )*, *ExtractHead( )*, and *ExtractTail( )*.

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;

}

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.

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.