This blog is under construction

Sunday 17 February 2013

Array Implementation Of Queue

Queue is a kind of ADT(abstract data type) that follows First In First Out(FIFO) principle. The process of inserting elements at the rear terminal position, known as enqueue and removal of elements from the front position, know as dequeue.

Queue
        ====================
front  11  |   22  | 33 | 44 |          rear
=====================

Enqueue:  Insert an element "55" at the rear terminal position.
                              Queue
               ==========================
front           11  |   22  | 33 | 44 | 55  |       rear
                ==========================

Dequeue:  Delete the element at the front position of the queue.
                              Queue
                =====================
front           22  |   33  | 44 | 55 |          rear
                =====================


Always create queue in circular fashion.  Consider a queue of size 4.

                            Queue
                ====================
                  22  |   33  | 44 |      |
                ====================
             front                        rear

Dequeue an element from the queue.
                            Queue
                ====================
                |      |   33  | 44 |       |
               =====================
                         front             rear

Insert 10 to the queue and the rear will move to the front of the queue.
                            Queue
               ======================
               |       |   33  | 44 |  10   |
              ======================
              rear    front      

rear = (rear + 1)  % sizeof (queue)
      = (3 + 1) % 4
        = 0 (so, 0 is the current rear position)

Example program for Array Implementation of Queue (wrapped around method):



  #include <stdio.h>
  #include <stdlib.h>

  int *queue, front = 0, rear = 0, n, size = 0;

  /* queue is empty or not */
  int isEmpty() {
        if (size == 0)
                return 1;
        else
                return 0;
  }

  /* insert an element into the queue */
  void enqueue(int data) {
        if (size == n)
                printf("Queue is full\n");
        else {
                queue[rear] = data;
                rear = (rear + 1) % n;
                size++;
        }
  }

  /* delete an element from the queue */
  void dequeue() {
        if (isEmpty())
                printf("Queue is Empty\n");
        else {
                queue[front] = 0;
                front = (front + 1) % n;
                size--;
        }
  }


  /* display elements present in the queue */
  void display() {
        int i, j = 0;
        printf("Elements in queue:");
        for (i = front; j < size; i = (i+1) % n, j++)
                        printf("%3d", queue[i]);
        printf("\n");
  }


  int main() {
        int data, ch;
        printf("Enter the size of the Queue:");
        scanf("%d", &n);
        queue = (int *)malloc(sizeof (int) * n);
        while (1) {
                printf("1. Enqueue\n2. Dequeue\n");
                printf("3. Size\n4. Is Empty\n5. Display\n");
                printf("6. Exit\nEnter ur choice:");
                scanf("%d", &ch);
                switch (ch) {
                        case 1:
                                printf("Enter the data to insert:");
                                scanf("%d", &data);
                                enqueue(data);
                                break;
                        case 2:
                                dequeue();
                                break;
                        case 3:
                                printf("No of elements in queue:%d\n", size);
                                break;
                        case 4:
                                if (isEmpty())
                                        printf("Queue is Empty\n");
                                else
                                        printf("Queue is available\n");
                                break;

                        case 5:
                                display();
                                break;
                        case 6:
                                exit(0);
                        default:
                                printf("Please retry with correct option\n");
                                break;
                }

        }
        return 0;
  }




  Output:(C Program For Array Implementation Of Queue)
  jp@jp-VirtualBox:$ ./a.out
  Enter the size of the Queue:3
  1. Enqueue
  2. Dequeue
  3. Size
  4. Is Empty
  5. Display
  6. Exit
  Enter ur choice:1
  Enter the data to insert:10
  1. Enqueue
  2. Dequeue
  3. Size
  4. Is Empty
  5. Display
  6. Exit
  Enter ur choice:1
  Enter the data to insert:20
  1. Enqueue
  2. Dequeue
  3. Size
  4. Is Empty
  5. Display
  6. Exit
  Enter ur choice:1
  Enter the data to insert:30
  1. Enqueue
  2. Dequeue
  3. Size
  4. Is Empty
  5. Display
  6. Exit
  Enter ur choice:1
  Enter the data to insert:40
  Queue is full
  1. Enqueue
  2. Dequeue
  3. Size
  4. Is Empty
  5. Display
  6. Exit
  Enter ur choice:5
  Elements in queue: 10 20 30
  1. Enqueue
  2. Dequeue
  3. Size
  4. Is Empty
  5. Display
  6. Exit
  Enter ur choice:2
  1. Enqueue
  2. Dequeue
  3. Size
  4. Is Empty
  5. Display
  6. Exit
  Enter ur choice:5
  Elements in queue: 20 30
  1. Enqueue
  2. Dequeue
  3. Size
  4. Is Empty
  5. Display
  6. Exit
  Enter ur choice:2
  1. Enqueue
  2. Dequeue
  3. Size
  4. Is Empty
  5. Display
  6. Exit
  Enter ur choice:5
  Elements in queue: 30
  1. Enqueue
  2. Dequeue
  3. Size
  4. Is Empty
  5. Display
  6. Exit
  Enter ur choice:2
  1. Enqueue
  2. Dequeue
  3. Size
  4. Is Empty
  5. Display
  6. Exit
  Enter ur choice:5
  Elements in queue:
  1. Enqueue
  2. Dequeue
  3. Size
  4. Is Empty
  5. Display
  6. Exit
  Enter ur choice:2
  Queue is Empty
  1. Enqueue
  2. Dequeue
  3. Size
  4. Is Empty
  5. Display
  6. Exit
  Enter ur choice:3
  No of elements in queue:0
  1. Enqueue
  2. Dequeue
  3. Size
  4. Is Empty
  5. Display
  6. Exit
  Enter ur choice:4
  Queue is Empty
  1. Enqueue
  2. Dequeue
  3. Size
  4. Is Empty
  5. Display
  6. Exit
  Enter ur choice:6




1 comment:

  1. thanks for providing all ds problem and many more in one place.

    ReplyDelete