Queues & Stacks - 1

COMP108 Lectures 2021-02-25

• Arrays - Alow random access to data.
• Queues - FIFO
• Stack - LIFO

Queues

There are two operations on a queue:

• Enqueue - Insert element to the tail.
• Dequeue - Delete element from the head.

The head points to the first element and the tail points to the location where data should be enqueued.

The actions are completed as follows:

• Enqueue
  • Save the data to Q[tail] and increment tail by 1.
• Dequeue
  • Retrieve data from Q[head] and increment head by 1.

Need to check if queue is empty before dequeue or full before enqueue.

Pseudo Code - Infinite Size

Enqueue(Q,x)
Q[tail] = x
tail++

Dequeue(Q)
if head == tail then # both pointers at same place
	Queue is EMPTY
else begin
	x = Q[head]
	head++
	return x
end

Pseudo Code - Limited Size

Enqueue(Q,x)
if tail > size then
	Queue is FULL
else begin
	Q[tail] = x
	tail++
end

Looping

In order to make use of free lower blocks the indexes must wrap around. This will give the following methods:

• Enqueue
  • After incrementing tail, if it exceeds size, then reset it to 1.
  • Same for checking full or not.
  • If indexes are from 0 to size - 1 you can use %.
• Dequeue
  • After incrementing head, if it exceeds size, then reset it to 1.
  • If indices are from 0 to size - 1, you can use %.