Queues

The main difference between a stack and a queue is that a stack is designed so that the last element added is the first element removed (LIFO) while a queue is designed so that the first element added is the first element removed (FIFO).

Like a stack, a queue is an array of strings, integers or real numbers. However, a queue needs two index pointers - one for the head of the queue and one for the tail. The use of two pointers alleviates the need shift the remaining elements in the array when one is removed. It is best to imagine the array is like a circle where the next element after the nth element is the first.

As with stacks, it is immaterial whether the queue grows upwards or downwards and whether the HEAD and TAIL variables point at the element in question or the next free space. However, if one of the pointers points to the element in question and the other to the the next free space then the status of the queue is automatically determined without the need for a counter variable. If HEAD = TAIL then the queue is empty and if HEAD and TAIL differ by 1 then the queue is full.

In the example below, the queue grows upwards, the TAIL variable (TL) points to the last added element and the HEAD variable (HD) points one below the next element to be removed. Rather than stopping the program if an attempt is made to remove an element from and empty queue or add one to a full queue, a variable (QS) is used to indicate the status of the operation. 0 = successful, 1 = queue full and 2 = queue empty.

10 MX=20:DIM Q$(MX):HD=1:TL=1:GOTO 1000
196 REM
197 REM PUSH - ADD E$ TO THE TAIL OF THE QUEUE
198 REM RETURN STATUS OF OPERATION IN QS
199 REM
200 IF TL=HD-1 OR (TL=MX AND HD=1) THEN QS=1:RETURN
210 QS=0:TL=TL+1:IF TL>MX THEN TL=1
220 Q$(TL)=E$:RETURN
296 REM
297 REM PULL - REMOVE E$ FROM THE HEAD OF THE QUEUE
298 REM RETURN STATUS OF OPERATION IN QS
299 REM
300 IF HD=TL THEN QS=2:RETURN
310 QS=0:HD=HD+1:IF HD>MX THEN HD=1
320 E$=Q$(HD):RETURN
1000 ...