Queues are slightly different from stacks as elements are added from one end, and removed from the other. This time, the implementation is also more complex with the use of a circular array. Read on to find out more.

What is a queue?

A queue is another data structure which is a linear sequence in which elements can only be added at one end, called the rear, and removed from the other, called the front. Queues are First In First Out (FIFO) structures. As the name suggests, queues act the same way as queues do in real life. People queue up from the back and exit from the front as the queue moves on. A computer uses queues to to manage waiting jobs to be processed. Jobs get appended at the back, while others are processed at the front.

How are queues implemented then?

This time, the implementation is a bit more difficult because we will be making use of a circular array. That means that after the last index of an array, it'll return to the first one again. Why do we want this? This is to shorten the code - If we had implemented it on a linear array, every time on element is removed, everything behind would have to be pushed up. In a circular array, all we need are two numbers to indicate the first and the last elements.

However, if we use a circular array, we wont be able to differentiate between an empty queue and a full one as in both cases, the indicators are next to one another. Therefore, we must give up one array index so as to make a 'full' array one where the indicator for the last element is two indexes away from the indicator for the first element.

There are four basic operations associated with a queue:

• init_queue
  initializes an empty queue
• empty_queue
  returns true if queue is empty
• add_q
  inserts element behind queue
• delete_q
  removes element at front of queue

Alright, let's start coding!

We'll start off first by declaring a constant, MAX, as the maximum number of elements. This way, we can easily increase the maximum height as needed.

  const
    MAX = 20;

  type
    int_Queue = record
                  int_array: array[0..MAX+1] of integer;
                  front, rear: integer;
                end;

  function head_q(q: int_Queue) : integer;
    begin
      if empty_q(q) then
        head_q := 0
      else
        head_q := a.int_array[q.front];
    end;

  function tail_q(q: int_Queue) : integer;
    begin
      if empty_q(q) then
        tail_q := 0
      else
        tail_q := a.int_array[q.rear];
    end;

  procedure init_q(var q: int_Queue);
    begin
      q.front := 0;
      q.rear := MAX+1;
    end;

  function next(current: integer) : integer;
    begin
      next := (current+1) mod MAX+1;
    end;

  function empty_q(q: int_Queue) : boolean;
    begin
      is_full := (next(q.rear) = q.front);
    end;

  function full_q(q: int_Queue) : integer;
    begin
      top := (next(next(q.rear)) = q.front);
    end;

  procedure add_q(var q: int_Queue; x: integer);
    begin
      if full_q(q) then
        Writeln('Queue Full')
      else
        begin
          q.rear := next(q.rear);
          q.int_array[q.rear] := x;
        end;
    end;

  function delete_q(q: int_Queue) : integer;
    begin
      if empty_q(q) then
        Writeln('Queue Empty')
      else
        begin
          q.front := next(q.front);
        end;
    end;