Representation of Queues in Data Structures
Queues may be represented in the computer in various ways, usually by means at:
We are using an array QUEUE with N elements. Observe that whenever an element is deleted from the queue, the value of FRONT is increased by 1.
Similarly, whenever an element is added to the queue, the value of REAR is increased by 1.
This means that after N insertions, the rear element of the queue will occupy QUEUE[N], or, in other words; eventually the queue will occupy the last part of array.
Suppose that our queue contains only one element, i.e., suppose that
Then, we assign
to indicate that the queue is empty.
- Linear arrays
- One-way lists.
Linear array in Queues
Unless otherwise stated or implied, each of our queues will be maintained by a linear array QUEUE and two pointer variables: FRONT, containing the location of the front element of the queue; and REAR, containing the location of the rear element of the queue. The condition FRONT = NULL will indicate that the queue is empty.We are using an array QUEUE with N elements. Observe that whenever an element is deleted from the queue, the value of FRONT is increased by 1.
FRONT := FRONT + 1
REAR := REAR + 1
This means that after N insertions, the rear element of the queue will occupy QUEUE[N], or, in other words; eventually the queue will occupy the last part of array.
Suppose that our queue contains only one element, i.e., suppose that
FRONT = REAR = NULL
and suppose that the element is deleted.Then, we assign
FRONT := NULL and
REAR := NULL
to indicate that the queue is empty.
Insertion in Queues Using Arrays
Algorithm: QINSERT(QUEUE, N, FRONT, REAR, ITEM).
This algorithm inserts an element ITEM into a queue.
Step I: [OVERFLOW?]
If FRONT = 1 and REAR = N, then: Write: OVERFLOW, and Exit.
Step II: [Find new value of REAR.]
If FRONT = NULL, then:
Set FRONT := 1 and REAR := 1. [When QUEUE empty.]
Else if REAR = N, then:
Set REAR := 1.
Else:
Set REAR := REAR + 1.
[End of If structure.]
Step III: Set QUEUE[REAR] := ITEM [This inserts new element.]
Step IV: Exit.
This algorithm deletes an element from a queue and assigns it to the variable ITEM.
Step I: [UNDERFLOW?]
If FRONT = NULL, then: Write: UNDERFLOW and Exit.
Step II: Set ITEM := QUEUE[FRONT].
[This copies the element of queue into ITEM.]
Step III: [Find new value of FRONT.]
If FRONT := REAR, then: [Queue has only one element to start.]
Set FRONT := NULL, and
REAR := NULL.
Else if FRONT := N, then:
Set FRONT := 1.
Else:
Set FRONT := FRONT + 1.
[End of If structure.]
Step IV: Exit.
Step I: [OVERFLOW?]
If FRONT = 1 and REAR = N, then: Write: OVERFLOW, and Exit.
Step II: [Find new value of REAR.]
If FRONT = NULL, then:
Set FRONT := 1 and REAR := 1. [When QUEUE empty.]
Else if REAR = N, then:
Set REAR := 1.
Else:
Set REAR := REAR + 1.
[End of If structure.]
Step III: Set QUEUE[REAR] := ITEM [This inserts new element.]
Step IV: Exit.
Deletion in Queues Using Arrays
Algorithm: QDELETE (QUEUE, N, FRONT, REAR, ITEM).This algorithm deletes an element from a queue and assigns it to the variable ITEM.
Step I: [UNDERFLOW?]
If FRONT = NULL, then: Write: UNDERFLOW and Exit.
Step II: Set ITEM := QUEUE[FRONT].
[This copies the element of queue into ITEM.]
Step III: [Find new value of FRONT.]
If FRONT := REAR, then: [Queue has only one element to start.]
Set FRONT := NULL, and
REAR := NULL.
Else if FRONT := N, then:
Set FRONT := 1.
Else:
Set FRONT := FRONT + 1.
[End of If structure.]
Step IV: Exit.
Post a Comment