Tuesday, October 17, 2006

Stacks and Queues

Topics

Stacks
- Stacks are extremely useful in programming.  They are a data structure analogous to a stack of plates in a cafeteria.
- The stack data structure allows you to "push" a value on the stack, and then "pop" the value off the stack later.   When you pop off the stack, you get the most recent value pushed on.
- Stacks work as "last one in is first one out"  or "last in - first out" or "lifo".
- Either an array or a linked list can be used for a stack.  Both are extremely efficient.  The array is a little faster, but has the limitation of a specific size.  Linked lists are efficient because you only need to add or remove from the head, not any interior nodes.
 

Example - an integer stack class

#include <iostream>
using namespace std;

#define DEFAULT_SIZE 10

using namespace std;

class Stack
{
public:

 // Construction
 Stack(int s);
 ~Stack();

 // Push on top of the stack
 bool push(int);

 // Pop off top of the stack
 bool pop(int&);

 // Is stack empty?
 bool isEmpty();
 

private:
 int* array;   // holds stack values
 int size;   // size of stack (optional)
 int top;    // top position on stack

};

// Constructor
Stack::Stack(int s)
{
 if (s > 0)
   size = s;
 else
   size = DEFAULT_SIZE;
 array = new int[size];
 top = -1;
}

// Destructor
Stack::~Stack()
{
 if( array ) delete[] array;
}

// push method
bool Stack::push(int value)
{
 if( top < size-1 ) (top always points where current top value is)
 {
  // Assign value to top position
  array[ ++top ] = value;
  return true;
 }
 else
 {
  // Cannot push any more values -- next line optional  
  // cout << "  Warning: stack overflow!" << endl;
  return false;
 }
}

// pop method
bool Stack::pop(int& value)
{
 if( top >= 0 ) (top always points where current top value is)
 {
   // Return top of stack, decrement top index
   value = array[ top-- ];
   return true;
 }
 else
 {
  // Cannot return any more values -- next line optional
  // cout << "  Warning: stack underflow!" << endl;
  return false;
 }

}
 

// isEmpty method
bool Stack::isEmpty()
{
 return (top == -1) ? true : false;
}

 

Example 1 - stack of integers

void main()
{
 Stack intstack(3);
 int value = 77;
 int i;

 // Pushing on stack
 for( i = 0; i < 3; ++i, value+=1 )
 {
  cout << "Pushing value: " << value << endl;
  intstack.push(value);
 }

 // Popping off stack
 for( i = 0; i < 3; ++i )
 {
  if (intstack.pop(value))
      cout << "Popped off value: " << value << endl;
 }
}

Output
Pushing value: 77
Pushing value: 78
Pushing value: 79
Popped off value: 79
Popped off value: 78
Popped off value: 77

 

- If you need maximal efficiency, you can implement a stack without anything more than an array, an integer variable, and a constant.
 

Example - minimal stack implementation, maximal efficiency

// initialization
datatype array* = new datatype[SIZE];
top = 0;

// push value on the stack (top always points where the next value will be put)
if (top < SIZE)
    array[top++] = value;

// pop value from the stack (top always points where the next value will be put)
if (top > 0)
    value = array[--top];

 
Queues  (Queen's English spelling - in England you don't "get in line", you "queue up")
- Queues are similar to stacks, but you put the value onto one end and take it off of the other end.
- The terminology usually used with queues it to "enqueue" a value onto the queue, and then "dequeue" a value off  the other end.  When you dequeue, you get the oldest remaining value on the queue.
- Queues work as "first one in is first one out"  or "first in - first out" or "fifo".
- In the theater and television, not to mention billiards and pool, you spell it "cue" .
 

Example - an integer queue class

#include <iostream>

#define DEFAULT_SIZE 10

using namespace std;

class Queue
{
public:

 // Construction
 Queue(int s);
 ~Queue();

 // Enqueue on the back of the queue
 bool enqueue(int);

 // Dequeue from the front of the queue
 bool dequeue(int&);

 // Is queue empty?
 bool isEmpty();
 

private:
 int* array;   // holds queue values
 int size;    // size of queue
 int front;  // front position on queue - use to dequeue
 int back;  // back position on queue - use to enqueue

};

// Constructor
Queue::Queue(int s)
{
 if (s > 0)
   size = s;
 else
   size = DEFAULT_SIZE;
 array = new int[size];
 front = back = 0;
}

// Destructor
Queue::~Queue()
{
 if( array ) delete[] array;
}

// enqueue method
bool Queue::enqueue(int value)
{
 // (front and back point to where they will get or put the next value)
 if( (back + 1) % size != front )
 {
  // Assign value to current position in back and
  //   increment the back position, jumping back to
  //   the front of the array if going off the end
  array[back] = value;
  back = ++back % size;
  return true;
 }
 else
 {
  // Queue's underlying array full -- next line optional  
  // cout << "  Warning: queue is full!" << endl;
  return false;
 }
}

// dequeue method
bool Queue::dequeue(int& value)
{
 // (front and back point to where they will get or put the next value)
 if( front != back )
 {
   // Return front of queue, then increment front index,
   //  jumping back to the beginning of array if at end.
   value = array[front];
   front = ++front % size;
   return true;
 }
 else
 {
  // Queue's array is empty -- next line optional
  // cout << "  Warning: queue empty!" << endl;
  return false;
 }
}
 

// isEmpty method
bool Queue::isEmpty()
{
 return (front == back) ? true : false;
}

 

Example 2 - queue of integers

void main()
{
 Queue intqueue(3);
 int value = 77;
 int i;

 // Pushing on queue
 for( i = 0; i < 3; ++i, value+=1 )
 {
  cout << "Enqueuing value: " << value << endl;
  intqueue.enqueue(value);
 }

 // Popping off queue
 for( i = 0; i < 3; ++i )
 {
  if (intqueue.dequeue(value))
      cout << "Dequeuing value: " << value << endl;
 }
}

Output
Enqueuing value: 77
Enqueuing value: 78
Enqueuing value: 79
Dequeuing value: 77
Dequeuing value: 78
Dequeuing value: 79
 
 

- If you need maximal efficiency, you can implement a queue similarly to a stack, but you need two integer variables.
 

Example - minimal queue implementation, maximal efficiency

// initialization
datatype queue* = new datatype[SIZE];
front = back = -1;  // front points at where it got the last value.
                    // back points at where it put the last value.

// enqueue value
if ((back + 1) % SIZE != front)
    queue[back = ++back % SIZE] = value;  //notice assignment inside the braces

// dequeue value
if (front != back)
    value = array[front = ++front % SIZE];//notice assignment inside the braces



Linked List implementation of stacks and queues
- Linked list implementations have the advantage of no limit in the size, except available computer memory.
- However, if you don't reclaim the memory of each node that is removed, then you would have a very serious memory leak.
- Linked list implementations are a little slower and take some additional memory.

- The stack data structure just requires that you add and remove from the head of the list.  The code just requires manipulating the head pointer and the next pointer of your new node. 
- The push itself, after the node is made, is just two assignment statements. 
- The pop is also two assignment statements, but they must be enclosed in an if statement to check for an empty stack.  

- The queue data structure just requires that you add to the tail (back) and remove from the head (front).  You will need two pointers, but the code itself is as simple as the stack implementation.
- The enqueue, after the node is made, is just two assignment statements. 
- The dequeue is also two assignment statements, but they must be enclosed in an if statement to check for an empty queue.  

 

Readings

Deitel & Deitel Fourth Edition: 11.1 - 11.4