CMSC--202 Computer Science II for Majors
Fall 1997 10 October 1997 Stacks and Queues

Abstract Data Types

An abstract data type has two parts:

1. a description of the elements making up the ADT, and,
2. a description of the operations permitted on the elements.

Note that an ADT NEVER involves implementation details.

Stack ADT

Here is an ADT for stack:

1. The elements are homogeneous. There is a notion of ``top'' of the stack.
2. The operations are:

   stack_type create_stack(void)

   Creates a new (empty) stack and returns it.

   void push(stack_item_type item, stack_type stack

   Adds the specified item to the top of the stack. It is an error to attempt to push an item onto a full stack.

   stack_item_type pop(stack_type stack)

   Returns the top item of the stack and removes it from the stack. It is an error to attempt to pop an item from an empty stack.

   BOOL empty_stack(stack_type stack)

   A predicate that returns TRUE if the stack is empty, FALSE otherwise.

   BOOL full_stack(stack_type stack)

   A predicate that returns TRUE if the stack is full, FALSE otherwise.

Queue ADT

Here is an ADT for queue:

1. The elements of a queue are homogeneous. There is a notion of ``front'' of a queue and ``rear'' of a queue.
2. The operations are:

   queue_type create_queue(void)

   Creates a new (empty) queue and returns it.

   void enqueue(queue_item_type item, queue_type queue)

   Adds the specified item to the rear of the queue. It is an error to attempt to enqueue an item into a full queue.

   queue_item_type dequeue(queue_type queue)

   Returns the item at the front of the queue and removes that item from the queue. It is an error to attempt to dequeue an item from an empty queue.

   BOOL empty_queue(queue_type queue)

   A predicate that returns TRUE if the queue is empty, FALSE otherwise.

   BOOL full_queue(queue_type queue)

   A predicate that returns TRUE if the queue is full, FALSE otherwise.

The stacks.h and queues.h interface files for the stack and queue operations are in the directory
anastasi/Public/202/Includes . The implementation of the operations is in the lib202.a archive in the directory anastasi/Public/202/Libraries .

A Stack Example: Checking for Balanced Parentheses

We use a stack which stores items of type char and assume the interface is in the file char_stack.h

#include "char_stack.h"
#include <stdio.h>

main()
{
   char_stack_type S;
   char c, d;
   int match = TRUE;

   while (there is more expression to read)
    {
      read a character, c;
      if (c is one of '(' or '{' or '[')
         push(c, S);
      else if (c is one of ')' or '}' or ']')
        {
          if (empty_stack(S) == TRUE) 
             { 
               match = FALSE;
               break;
             }
          d = pop(S);
          if (!MatchingParens(c, d))
             {
               match = FALSE;
               break;
             }
        }
     }
    if (empty_stack(S) == FALSE) match = FALSE;
    if (match == TRUE) 
       printf("Parentheses match");
    else
       printf("Parentheses do not match");
}

Other Uses for Stacks

• Evaluation of postfix expressions.
• Simulating recursion.
• Reversing strings, lists, etc.
• Compiling using recursive descent.
• Any LIFO system.

Stack Implementations

We examine two implementations for stacks, a list implementation and an array implementation. The major differences between the two implementations are:

1. The array implementation has a maximum size dictated by the size of the array. The list implementation has no maximum size.
2. The array implementation requires storage space for just the stack items. The list implementation may additionally require storage for pointers to link the stack items together.

List Implementation of Stack

Note that although there is no maximum size for a stack implemented as a list, we nonetheless define the operation full_stack in order to maintain the same interface for each implementation. Note also that we represent a stack as a pointer to a list; this allows the routines that need to modify the stack passed to them to do so, even though the stack is passed by value.

The interface file

typedef list_type *stack_type;
typedef list_item_type stack_item_type;

The implementation file

stack_type create_stack(void)
{
  stack_type result;
  result = (stack_type) malloc(sizeof(list_type));
  assert(result != NULL);  
  *result = the_empty_list;
  return result;
}

void push(stack_item_type item, stack_type stack)
{
  *stack = cons(item, *stack);
}

stack_item_type pop(stack_type stack)
{
  stack_item_type result;
  assert(empty_stack(stack) == FALSE);
  result = first(*stack);
  *stack = rest(*stack);
  return result;
}

BOOL empty_stack(stack_type stack)
{
  return (empty_list(*stack)) ? TRUE : FALSE;
}

BOOL full_stack(stack_type stack)
{
  return FALSE;
}

Array Implementation of Stack

Notice that the headers for the five functions are exactly the same as for the list implementation. This allows the array implementation to be substituted for the list implementation with no change in the code that uses stacks. The choices of int for stack_item_type and of 128 for MAX_STACK_SIZE are arbitrary -- just to have a specific example.

The interface file

#define MAX_STACK_SIZE 128

typedef int stack_item_type;
typedef struct stack_struct
    {
      int count;
      stack_item_type items[MAX_STACK_SIZE];
    } *stack_type;

The implementation file

stack_type create_stack(void)
{
  stack_type result;
  result = (stack_type) malloc(sizeof(struct stack_struct));
  assert(result != NULL);  
  result->count = 0;
  return result;
}

void push(stack_item_type item, stack_type stack)
{
  assert(full_stack(stack) == FALSE);
  stack->items[stack->count] = item;
  stack->count++;
}

stack_item_type pop(stack_type stack)
{
  assert(empty_stack(stack) == FALSE);
  stack->count--;
  return stack->items[stack->count];
}

BOOL empty_stack(stack_type stack)
{
  return (stack->count == 0) ? TRUE : FALSE;
}

BOOL full_stack(stack_type stack)
{
  return (stack->count == MAX_STACK_SIZE) ? TRUE : FALSE;
}

Queue Implementations

We present three implementations for queues, a list implementation, an array implementation, and a pointer-based implementation. The major differences among the three implementations are:

1. The array implementation has a maximum size, the list and pointer implementations have no maximum size.
2. The array implementation stores only the items, the pointer implementation must also store pointers. Depending on the list implementation, it too may store pointers.
3. The pointer implementation explicitly frees storage upon dequeueing, the list implementation does not explicitly do so. Our list implementation does not free storage.
4. The pointer and array implementations perform the enqueue operation without the need to traverse the entire queue to find its end. This means the pointer and array implementations are more efficient than the list implementation for enqueue.
5. The pointer and array implementations do not build an entirely new list for each enqueue operation, our list implementation does. Depending on garbage-collecting facilities, this may mean that the array and pointer implementations are more space-efficient than the list implementation.

List Implementation of Queues

This implementation requires the ability to add an item to the end of a list. This can be done using only the primitive list operations without any knowledge of how lists are implemented. Note that append_to_end constructs an entirely new list.

list_type append_to_end(list_type list, list_item_type item)
{
  if (empty_list(list) == TRUE)
    return cons(item, the_empty_list);
  return cons(first(list), append_to_end(rest(list), item));
}

The Interface File

typedef list_type *queue_type;
typedef list_item_type queue_item_type;

The Implementation File

queue_type create_queue(void)
{
  queue_type result;
  result = (queue_type) malloc(sizeof(list_type));
  assert(result != NULL);
  *result = the_empty_list;
  return result;
}

void enqueue(queue_item_type item, queue_type q)
{
   *q = append_to_end(*q, item);
}

queue_item_type dequeue(queue_type q)
{
   queue_item_type result;
   assert(empty_queue(q) == FALSE);
   result = first(*q);
   *q = rest(*q);
   return result;
}

BOOL empty_queue(queue_type q)
{
  return empty_list(*q);
}

BOOL full_queue(queue_type q)
{
  return FALSE;
}

Pointer Implementation of Queues

In this implementation, a queue is defined to be a pointer to a struct that contains pointers to the front and the rear of a queue. Keeping a pointer to the rear makes the enqueue operation quite efficient. Also, storage is explicitly freed when a dequeue operation is done. The choice of int for queue_item_type is arbitrary.

The Interface File

typedef int queue_item_type;
typedef struct queue_node_struct
  {
   queue_item_type data;
   struct queue_node_struct *next;
  } *queue_node_ptr;
typedef struct queue_struct
  {
    queue_node_ptr front;
    queue_node_ptr rear;
  } *queue_type;

The Implementation File

queue_type create_queue(void)
{
  queue_type result;
  result = (queue_type) malloc(sizeof(struct queue_struct));
  assert(result != NULL);
  result->front = NULL;  /* indicates an empty queue */
  result->rear  = NULL;  /* just for neatness */
  return result;
}

void enqueue(queue_item_type item, queue_type q)
{
  queue_node_ptr temp;
  temp = (queue_node_ptr) malloc(sizeof(struct queue_node_struct));
  assert(temp != NULL);
  temp->data = item;
  temp->next = NULL;
  if (empty_queue(q) == TRUE) 
    q->front = temp;
  else 
    q->rear->next = temp;
  q->rear = temp;
}

queue_item_type dequeue(queue_type q)
{
  queue_node_ptr temp;
  queue_item_type result;
  assert(empty_queue(q) == FALSE);
  temp = q->front;
  q->front = q->front->next;
  result = temp->data;
  if (empty_queue(q) == TRUE)
    q->rear = NULL;  /* just for neatness */
  free(temp);
  return result;
}

BOOL empty_queue(queue_type q)
{
  return (q->front == NULL) ? TRUE : FALSE;
}

BOOL full_queue(queue_type q)
{
  return FALSE;
}

Array Implementation of Queue

The C modulus operator (%) is used to ``wrap around'' the end of the array when a subscript to the array becomes too large. This approach is called a ``circular array'' because the array acts as if it were in a circle rather than a line. The choices of int for queue_item_type and of 128 for MAX_QUEUE_SIZE are arbitrary.

The Interface File

#define MAX_QUEUE_SIZE 128

typedef int queue_item_type;
typedef queue_item_type queue_array[MAX_QUEUE_SIZE];
typedef struct queue_struct
  {
    queue_array items;
    int front;
    int count;
  } *queue_type;

The Implementation File

queue_type create_queue(void)
{
  queue_type result;
  result = (queue_type) malloc(sizeof(struct queue_struct));
  assert(result != NULL);
  result->front = 0;
  result->count = 0;
  return result;
}

void enqueue(queue_item_type item, queue_type q)
{
  assert(full_queue(q) == FALSE);
  q->items[(q->front + q->count) % MAX_QUEUE_SIZE] = item;
  q->count++;
}

queue_item_type dequeue(queue_type q)
{
  queue_item_type result;
  assert(empty_queue(q) == FALSE);
  result = q->items[q->front];
  q->front = (q->front + 1) % MAX_QUEUE_SIZE;
  q->count--;
  return result;
}

BOOL empty_queue(queue_type q)
{
  return (q->count == 0) ? TRUE : FALSE;
}

BOOL full_queue(queue_type q)
{
  return (q->count == MAX_QUEUE_SIZE) ? TRUE : FALSE;
}

Exercises

1. Write a program that reads in numbers from the standard input until end-of-file, then prints the numbers in reverse order.
2. Write the function copy_queue that takes a queue_type as its argument and returns another queue_type as its result. The return queue must contain all of the items in the original queue in the same order that they were found in the original queue. The original queue must end up unchanged. Your function must lie above the queue abstraction barrier ( i.e., all manipulation of queues must be done using create_queue, enqueue, dequeue, and empty_queue).