Simple Queue

A simple queue is the normal queue implemented using an array or linked list.

Array Representation

Use two variables:

Example:

Index: 0   1   2   3   4
Data : 10  20  30  _   _
        ^       ^
      front    rear

enqueue(x):
    if rear == MAX - 1:
        overflow
    if front == -1:
        front = 0
    rear = rear + 1
    queue[rear] = x

Time: O(1)

dequeue():
    if front == -1 or front > rear:
        underflow
    x = queue[front]
    front = front + 1
    return x

Time: O(1)

peekFront():
    return queue[front]

Time: O(1)

display():
    for i from front to rear:
        print queue[i]

Time: O(n)

After several dequeues, the front moves right and free spots on the left cannot be reused easily in the simple array version.

This waste is called false overflow.