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:
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;As mentioned before, each stack is made up of a circular array, and two numbers indicating its first and last members. Since we want to make it modular, let's make our own type definition. (To learn more about user defined types, look up 'type' in the online help.)
type int_Queue = record int_array: array[0..MAX+1] of integer; front, rear: integer; end;Now let's code all the four basic operations with its supporting code. Notice that we test whether the queue is full by testing if the rear is two indexes away from the front.
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;Modify these procedures as you want to fit your needs. All the examples so far have been for integers, you can try it for strings, records, and other data types. Well, that's it for queues. Enjoy!