CS13002 Programming and Data Structures

Spring semester

Stacks and queues

Stacks and queues are special kinds of ordered lists in which insertion and deletion are restricted only to some specific positions. They are very important tools for solving many useful computational problems. Since we have already implemented ordered lists in the most general form, we can use these to implement stacks and queues. However, because of the special insertion and deletion patterns for stacks and queues, the ADT functions can be written to be much more efficient than the general functions. Given the importance of these new ADTs, it is worthwhile to devote time to these special implementations.

The stack ADT and its applications

A stack is an ordered list of elements in which elements are always inserted and deleted at one end, say the beginning. In the terminology of stacks, this end is called the top of the stack, whereas the other end is called the bottom of the stack. Also the insertion operation is called push and the deletion operation is called pop. The element at the top of a stack is frequently referred, so we highlight this special form of getElement.
A stack ADT can be specified by the following basic operations. Once again we assume that we are maintaining a stack of characters. In practice, the data type for each element of a stack can be of any data type. Characters are chosen as place-holders for simplicity.

S = init();
Initialize S to an empty stack.
isEmpty(S);
Returns "true" if and only if the stack S is empty, i.e., contains no elements.
isFull(S);
Returns "true" if and only if the stack S has a bounded size and holds the maximum number of elements it can.
top(S);
Return the element at the top of the stack S, or error if the stack is empty.
S = push(S,ch);
Push the character ch at the top of the stack S.
S = pop(S);
Pop an element from the top of the stack S.
print(S);
Print the elements of the stack S from top to bottom.

An element popped out of the stack is always the last element to have been pushed in. Therefore, a stack is often called a Last-In-First-Out or a LIFO list.
Applications of stacks
Stacks are used in a variety of applications. While some of these applications are "natural", most other are essentially "pedantic". Here is a list anyway.

For processing nested structures, like checking for balanced parentheses, evaluation of postfix expressions.
For handling function calls and, in particular, recursion.
For searching in special data structures (depth-first search in graphs and trees), for example, for implementing backtracking.

Animation example : Use of stacks to evaluate postfix expressions

Interactive animation : Use of stacks to evaluate postfix expressions

Implementations of the stack ADT

A stack is specified by the ordered collection representing the content of the stack together with the choice of the end of the collection to be treated as the top. The top should be so chosen that pushing and popping can be made as far efficient as possible.
Using static arrays

Static arrays can realize stacks of a maximum possible size. If we assume that the stack elements are stored in the array starting from the index 0, it is convenient to take the top as the maximum index of an element in the array. Of course, the other choice, i.e., the other boundary 0, can in principle be treated as the top, but insertions and deletions at the location 0 call for too many relocations of array elements. So our original choice is definitely better.
   #define MAXLEN 100

   typedef struct {
      char element[MAXLEN];
      int top;
   } stack;

   stack init ()
   {
      stack S;

      S.top = -1;
      return S;
   }

   int isEmpty ( stack S )
   {
      return (S.top == -1);
   }

   int isFull ( stack S )
   {
      return (S.top == MAXLEN - 1);
   }

   char top ( stack S )
   {
      if (isEmpty(S)) {
         fprintf(stderr, "top: Empty stack\n");
         return '\0';
      }
      return S.element[S.top];
   }

   stack push ( stack S , char ch )
   {
      if (isFull(S)) {
         fprintf(stderr, "push: Full stack\n");
         return S;
      }
      ++S.top;
      S.element[S.top] = ch;
      return S;
   }

   stack pop ( stack S )
   {
      if (isEmpty(S)) {
         fprintf(stderr, "pop: Empty stack\n");
         return S;
      }
      --S.top;
      return S;
   }

   void print ( stack S )
   {
      int i;

      for (i = S.top; i >= 0; --i) printf("%c",S.element[i]);
   }
Here is a possible main() function calling these routines:
   int main ()
   {
      stack S;

      S = init(); printf("Current stack : "); print(S); printf(" with top = %c.\n", top(S));
      S = push(S,'d'); printf("Current stack : "); print(S); printf(" with top = %c.\n", top(S));
      S = push(S,'f'); printf("Current stack : "); print(S); printf(" with top = %c.\n", top(S));
      S = push(S,'a'); printf("Current stack : "); print(S); printf(" with top = %c.\n", top(S));
      S = pop(S); printf("Current stack : "); print(S); printf(" with top = %c.\n", top(S));
      S = push(S,'x'); printf("Current stack : "); print(S); printf(" with top = %c.\n", top(S));
      S = pop(S); printf("Current stack : "); print(S); printf(" with top = %c.\n", top(S));
      S = pop(S); printf("Current stack : "); print(S); printf(" with top = %c.\n", top(S));
      S = pop(S); printf("Current stack : "); print(S); printf(" with top = %c.\n", top(S));
      S = pop(S); printf("Current stack : "); print(S); printf(" with top = %c.\n", top(S));
   }
Here is the complete program. The output of the program is given below:
   top: Empty stack
   Current stack :  with top = .
   Current stack : d with top = d.
   Current stack : fd with top = f.
   Current stack : afd with top = a.
   Current stack : fd with top = f.
   Current stack : xfd with top = x.
   Current stack : fd with top = f.
   Current stack : d with top = d.
   top: Empty stack
   Current stack :  with top = .
   pop: Empty stack
   top: Empty stack
   Current stack :  with top = .
Animation example : Implementation of stacks with static memory

Using dynamic linked lists

As we have seen earlier, it is no big deal to create and maintain a dynamic list of elements. The only consideration now is to decide whether the beginning or the end of the list is to be treated as the top of the stack. Deletion becomes costly, if we choose the end of the list as the top. Choosing the beginning as the top makes the implementations of both push and pop easy. So we stick to this convention. As usual, we maintain a dummy node at the top (beginning) for simplifying certain operations. The ADT functions are implemented below:
   typedef struct _node {
      char element;
      struct _node *next;
   } node;

   typedef node *stack;

   stack init ()
   {
      stack S;

      /* Create the dummy node */
      S = (node *)malloc(sizeof(node));
      S -> element = '\0';
      S -> next = NULL;
      return S;
   }

   int isEmpty ( stack S )
   {
      return (S -> next == NULL);
   }

   int isFull ( stack S )
   {
      /* With dynamic memory the stack never gets full. However, a new
        allocation request may fail because of memory limitations. That may
        better be checked immediately after each malloc statement is executed.
        For simplicity we avoid this check in this implementation. */
      return 0;
   }

   char top ( stack S )
   {
      if (isEmpty(S)) {
         fprintf(stderr, "top: Empty stack\n");
         return '\0';
      }
      return S -> next -> element;
   }

   stack push ( stack S , char ch )
   {
      node *T;

      if (isFull(S)) {
         fprintf(stderr, "push: Full stack\n");
         return S;
      }

      /* Copy the new element in the dummy node */
      S -> element = ch;

      /* Create a new dummy node */
      T = (node *)malloc(sizeof(node));
      T -> element = '\0';
      T -> next = S;
      return T;
   }

   stack pop ( stack S )
   {
      if (isEmpty(S)) {
         fprintf(stderr, "pop: Empty stack\n");
         return S;
      }

      /* Treat the stack top as the new dummy node */
      S -> next -> element = '\0';
      return S -> next;
   }

   void print ( stack S )
   {
      node *T;

      T = S -> next;
      while (T != NULL) {
         printf("%c", T -> element);
         T = T -> next;
      }
   }
These new functions are compatible with the main() function of the implementation using arrays. The complete program is here.

Animation example : Implementation of stacks with dynamic linked lists
The queue ADT and its applications

A queue is like a "natural" queue of elements. It is an ordered list in which all insertions occur at one end called the back or rear of the queue, whereas all deletions occur at the other end called the front or head of the queue. In the popular terminology, insertion and deletion in a queue are respectively called the enqueue and the dequeue operations. The element dequeued from a queue is always the first to have been enqueued among the elements currently present in the queue. In view of this, a queue is often called a First-In-First-Out or a FIFO list.
The following functions specify the operations on the queue ADT. We are going to maintain a queue of characters. In practice, each element of a queue can be of any well-defined data type.

Q = init();
Initialize the queue Q to the empty queue.
isEmpty(Q);
Returns "true" if and only if the queue Q is empty.
isFull(Q);
Returns "true" if and only if the queue Q is full, provided that we impose a limit on the maximum size of the queue.
front(Q);
Returns the element at the front of the queue Q or error if the queue is empty.
Q = enqueue(Q,ch);
Inserts the element ch at the back of the queue Q. Insertion request in a full queue should lead to failure together with some appropriate error messages.
Q = dequeue(Q);
Delete one element from the front of the queue Q. A dequeue attempt from an empty queue should lead to failure and appropriate error messages.
print(Q);
Print the elements of the queue Q from front to back.

Applications of queues

For implementing any "natural" FIFO service, like telephone enquiries, reservation requests, traffic flow, etc.
For implementing any "computational" FIFO service, for instance, to access some resources. Examples: printer queues, disk queues, etc.
For searching in special data structures (breadth-first search in graphs and trees).
For handling scheduling of processes in a multitasking operating system.

Animation example : Use of queues for round-robin scheduling

Implementations of the queue ADT

Continuing with our standard practice followed so far, we are going to provide two implementations of the queue ADT, the first using static memory, the second using dynamic memory. The implementations aim at optimizing both the insertion and deletion operations.
Using static arrays

Recall that in our implementation of the "ordered list" ADT we always let the list start from the array index 0. This calls for relocation of elements of the list in the supporting array after certain operations (usually deletion). Now we plan to exploit the specific insertion and deletion patterns in queues to avoid these costly relocations.
We maintain two indices to represent the front and the back of the queue. During an enqueue operation, the back index is incremented and the new element is written in this location. For a dequeue operation, on the other hand, the front is simply advanced by one position. It then follows that the entire queue now moves down the array and the back index may hit the right end of the array, even when the size of the queue is smaller than the capacity of the array.
In order to avoid waste of space, we allow our queue to wrap at the end. This means that after the back pointer reaches the end of the array and needs to proceed further down the line, it comes back to the zeroth index, provided that there is space at the beginning of the array to accommodate new elements. Thus, the array is now treated as a circular one with index MAXLEN treated as 0, MAXLEN + 1 as 1, and so on. That is, index calculation is done modulo MAXLEN. We still don't have to maintain the total queue size. As soon as the back index attempts to collide with the front index modulo MAXLEN, the array is considered to be full.
There is just one more problem to solve. A little thought reveals that under this wrap-around technology, there is no difference between a full queue and an empty queue with respect to arithmetic modulo MAXLEN. This problem can be tackled if we allow the queue to grow to a maximum size of MAXLEN - 1. This means we are going to lose one available space, but that loss is inconsequential. Now the condition for full array is that the front index is two locations ahead of the back modulo MAXLEN, whereas the empty array is characterized by that the front index is just one position ahead of the back again modulo MAXLEN.
An implementation of the queue ADT under these design principles is now given.
   #define MAXLEN 100

   typedef struct {
      char element[MAXLEN];
      int front;
      int back;
   } queue;

   queue init ()
   {
      queue Q;

      Q.front = 0;
      Q.back = MAXLEN - 1;
      return Q;
   }

   int isEmpty ( queue Q )
   {
      return (Q.front == (Q.back + 1) % MAXLEN);
   }

   int isFull ( queue Q )
   {
      return (Q.front == (Q.back + 2) % MAXLEN);
   }

   char front ( queue Q )
   {
      if (isEmpty(Q)) {
         fprintf(stderr,"front: Queue is empty\n");
         return '\0';
      }
      return Q.element[Q.front];
   }

   queue enqueue ( queue Q , char ch )
   {
      if (isFull(Q)) {
         fprintf(stderr,"enqueue: Queue is full\n");
         return Q;
      }
      ++Q.back;
      if (Q.back == MAXLEN) Q.back = 0;
      Q.element[Q.back] = ch;
      return Q;
   }

   queue dequeue ( queue Q )
   {
      if (isEmpty(Q)) {
         fprintf(stderr,"dequeue: Queue is empty\n");
         return Q;
      }
      ++Q.front;
      if (Q.front == MAXLEN) Q.front = 0;
      return Q;
   }

   void print ( queue Q )
   {
      int i;

      if (isEmpty(Q)) return;
      i = Q.front;
      while (1) {
         printf("%c", Q.element[i]);
         if (i == Q.back) break;
         if (++i == MAXLEN) i = 0;
      }
   }
Here is a sample main() for these functions.
   int main ()
   {
      queue Q;

      Q = init(); printf("Current queue : "); print(Q); printf("\n");
      Q = enqueue(Q,'h'); printf("Current queue : "); print(Q); printf("\n");
      Q = enqueue(Q,'w'); printf("Current queue : "); print(Q); printf("\n");
      Q = enqueue(Q,'r'); printf("Current queue : "); print(Q); printf("\n");
      Q = dequeue(Q); printf("Current queue : "); print(Q); printf("\n");
      Q = dequeue(Q); printf("Current queue : "); print(Q); printf("\n");
      Q = enqueue(Q,'c'); printf("Current queue : "); print(Q); printf("\n");
      Q = dequeue(Q); printf("Current queue : "); print(Q); printf("\n");
      Q = dequeue(Q); printf("Current queue : "); print(Q); printf("\n");
      Q = dequeue(Q); printf("Current queue : "); print(Q); printf("\n");
   }
Finally, this is the output of the complete program.
   Current queue :
   Current queue : h
   Current queue : hw
   Current queue : hwr
   Current queue : wr
   Current queue : r
   Current queue : rc
   Current queue : c
   Current queue :
   dequeue: Queue is empty
   Current queue :
Animation example : Implementation of queues with static memory

Using dynamic linked lists

Linked lists can be used for implementing queues. We plan to maintain a dummy node at the beginning and two pointers, the first pointing to this dummy node and the second pointing to the last element. Both insertion and deletion are easy at the beginning. Insertion is easy at the end, but deletion is difficult at the end, since we have to move the pointer at the end one step back and there is no way other than traversing the entire list in order to trace the new end. So the natural choice is to take the beginning of the linked list as the front of the queue and the end of the list as the back of the queue.
The corresponding implementation is detailed below:
   typedef struct _node {
      char element;
      struct _node *next;
   } node;

   typedef struct {
      node *front;
      node *back;
   } queue;

   queue init ()
   {
      queue Q;

      /* Create the dummy node */
      Q.front = (node *)malloc(sizeof(node));
      Q.front -> element = ' ';
      Q.front -> next = NULL;
      Q.back = Q.front;
      return Q;
   }

   int isEmpty ( queue Q )
   {
      return (Q.front == Q.back);
   }

   int isFull ( queue Q )
   {
      return 0;
   }

   char front ( queue Q )
   {
      if (isEmpty(Q)) {
         fprintf(stderr,"front: Queue is empty\n");
         return '\0';
      }
      return Q.front -> element;
   }

   queue enqueue ( queue Q , char ch )
   {
      node *C;
      if (isFull(Q)) {
         fprintf(stderr,"enqueue: Queue is full\n");
         return Q;
      }

      /* Create new node */
      C = (node *)malloc(sizeof(node));
      C -> element = ch;
      C -> next = NULL;

      /* Adjust the back of queue */
      Q.back -> next = C;
      Q.back = C;

      return Q;
   }

   queue dequeue ( queue Q )
   {
      if (isEmpty(Q)) {
         fprintf(stderr,"dequeue: Queue is empty\n");
         return Q;
      }

      /* Make the front of the queue the new dummy node */
      Q.front = Q.front -> next;
      Q.front -> element = '\0';

      return Q;
   }

   void print ( queue Q )
   {
      node *G;

      G = Q.front -> next;
      while (G != NULL) {
         printf("%c", G -> element);
         G = G -> next;
      }
   }
And here is the program with a main() identical to that for the array implementation.

Animation example : Implementation of queues with dynamic linked lists
Course home