Operations in Queue, Enqueue and Dequeue

Queue

The queue is a non-primitive, homogeneous, FIFO data structure where deletion occurs from one end called Front or Head and insertion from the other end called theRear or the Tail.

A queue works like a line at the movies: the first person to join the rear of the line is the first person to reach the front of the line and buy a ticket. The last person to line up is the last person to buy a ticket (or—if the show is sold out—to fail to buy a ticket).

There are various queues quietly doing their job in your computer’s (or the network’s) operating system. There’s a printer queue where print jobs wait for the printer to be available. A queue also stores keystroke data as you type at the keyboard. This way, if you’re using a word processor but the computer is briefly doing something else when you hit a key, the keystroke won’t be lost; it waits in the queue until the word processor has time to read it. Using a queue guarantees the keystrokes stay in order until they can be processed.

The basic operations in a queue are

- Create Queue

- Enqueue (Insert Items)

- Dequeue (Remove Items)

- Display Items

Queue as an ADT

/* value definition */

abstract typedef Queue (eltype);

/* check for empty */

abstract empty(q)

Queue(eltype) q;

postcondition: empty == (len(q) == 0);

/* remove item */

abstract eltype remove(q)

precondition: empty(q) == False;

postcondition: remove == first(q);

q == sub(q, 1, len(q)-1);

/*insert item */

abstract insert(q, item)

Queue(eltype) q;

eltype item;

postcondition: q == q + ;

Implementation of Queue (Linear):

Algorithm:

1. Declare and initialize necessary variables

front = 0

rear = -1

MAXSIZE

Queue[]

item

2. For Enqueue Operation:

If rear >= MAXSIZE -1 :

Queue is full

Else:

Read item from user

rear = rear + 1

Queue[rear] = item

For next Enqueue, repeat step 2.

3. For Dequeue Operation:

If front > rear:

Queue is empty

Else:

item = Queue[front]

front = front + 1

For next Dequeue, repeat step 3.

References:

1. Y. Langsam, M. J. Augenstein and A. M Tenenbaum, “Data Structuresusing C and C++”

2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, “Introduction toAlgorithms”

3. G. Brassard and P. Bratley, “Fundamentals of Algorithms”

4. R. L. Kruse, B. P. Leung, C. L. Tondo, “Data Structure and Program designin C”

5. L, Robert. "Data Structures and Algorithms in24Hours"