{"id":26878,"date":"2017-12-26T20:37:32","date_gmt":"2017-12-26T15:07:32","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26878"},"modified":"2017-12-26T20:37:32","modified_gmt":"2017-12-26T15:07:32","slug":"java-programming-queue-data-structure-introduction-and-array-implementation","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-programming-queue-data-structure-introduction-and-array-implementation\/","title":{"rendered":"Java Programming-Queue-Data Structure-Introduction and Array Implementation"},"content":{"rendered":"

Like Stack<\/a>, Queue\u00a0<\/a>is a linear structure which follows a particular order in which the operations are performed.<\/span> The order is F<\/strong>irst I<\/strong>n F<\/strong>irst O<\/strong>ut (FIFO). \u00a0A good example of queue is any queue of consumers for a resource where the consumer that came first is served first.
\nThe difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.<\/p>\n

Operations on Queue:<\/strong>
\nMainly the following four basic operations are performed on queue:<\/p>\n

Enqueue:\u00a0<\/strong>Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition.
\nDequeue:<\/strong>\u00a0Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition.
\nFront:\u00a0<\/strong>Get the front item from queue.
\nRear:<\/strong> Get the last item from queue.<\/p>\n

\"Queue-Data<\/p>\n

Applications of Queue:<\/strong>
\nQueue is used when things don\u2019t have to be processed immediatly, but have to be processed in\u00a0F<\/strong>irst\u00a0I<\/strong>nF<\/strong>irst\u00a0O<\/strong>ut order like\u00a0Breadth First Search<\/a>. This property of Queue makes it also useful in following kind of scenarios.<\/p>\n

1)<\/strong>\u00a0When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk Scheduling.
\n2)\u00a0<\/strong>When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes. Examples include IO Buffers, pipes, file IO, etc.<\/p>\n

See\u00a0this\u00a0<\/a>for more detailed applications of Queue and Stack.<\/p>\n[ad type=”banner”]\n

Array implementation Of Queue<\/strong>
\nFor implementing queue, we need to keep track of two indices, front and rear. We enqueue an item at the rear and dequeue an item from front. If we simply increment front and rear indices, then there may be problems, front may reach end of the array. The solution to this problem is to increase front and rear in circular manner (See this <\/a>for details)<\/p>\n

Java \u00a0Programming<\/strong><\/p>\n

<\/div> 
\/\/ Java program for array implementation of queue  \/\/ A class to represent a queueclass Queue{    int front, rear, size;    int  capacity;    int array[];          public Queue(int capacity) {         this.capacity = capacity;         front = this.size = 0;          rear = capacity - 1;         array = new int[this.capacity];               }          \/\/ Queue is full when size becomes equal to     \/\/ the capacity     boolean isFull(Queue queue)    {  return (queue.size == queue.capacity);    }          \/\/ Queue is empty when size is 0    boolean isEmpty(Queue queue)    {  return (queue.size == 0); }          \/\/ Method to add an item to the queue.     \/\/ It changes rear and size    void enqueue( int item)    {        if (isFull(this))            return;        this.rear = (this.rear + 1)%this.capacity;        this.array[this.rear] = item;        this.size = this.size + 1;        System.out.println(item+ " enqueued to queue");    }          \/\/ Method to remove an item from queue.      \/\/ It changes front and size    int dequeue()    {        if (isEmpty(this))            return Integer.MIN_VALUE;                  int item = this.array[this.front];        this.front = (this.front + 1)%this.capacity;        this.size = this.size - 1;        return item;    }          \/\/ Method to get front of queue    int front()    {        if (isEmpty(this))            return Integer.MIN_VALUE;                  return this.array[this.front];    }           \/\/ Method to get rear of queue    int rear()    {        if (isEmpty(this))            return Integer.MIN_VALUE;                  return this.array[this.rear];    }}     \/\/ Driver classpublic class Test{    public static void main(String[] args)     {        Queue queue = new Queue(1000);                   queue.enqueue(10);        queue.enqueue(20);        queue.enqueue(30);        queue.enqueue(40);               System.out.println(queue.dequeue() +                      " dequeued from queue\\n");               System.out.println("Front item is " +                                queue.front());                  System.out.println("Rear item is " +                                 queue.rear());    }} <\/code><\/pre> <\/div>\n
Output:<\/p>\n
10 enqueued to queue\r\n20 enqueued to queue\r\n30 enqueued to queue\r\n40 enqueued to queue\r\n10 dequeued from queue\r\nFront item is 20\r\nRear item is 40<\/pre>\n
Time Complexity:<\/strong> Time complexity of all operations like enqueue(), dequeue(), isFull(), isEmpty(), front() and rear() is O(1). There is no loop in any of the operations.<\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
queue data structure introduction array implementation Like Stack, Queue is a linear structure which follows a particular order in which the operations<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,73012,2139],"tags":[80209,80203,80208,80207,80205,80204,80206,80200,80202,70068,80210,75626,80198,80199,80201],"class_list":["post-26878","post","type-post","status-publish","format-standard","hentry","category-coding","category-data-structures","category-java","tag-advantages-and-disadvantages-of-array-in-data-structure","tag-algorithm-for-insertion-and-deletion-in-queue","tag-application-of-array-in-data-structure","tag-array-in-data-structure-and-algorithm","tag-array-in-data-structure-pdf","tag-array-in-data-structure-with-example","tag-array-operations-in-data-structure-ppt","tag-circular-queue-using-array-in-c","tag-implementation-of-queue-using-array-in-data-structure","tag-linear-array-in-data-structure","tag-one-dimensional-array-in-data-structure","tag-queue-in-c-using-linked-list","tag-queue-in-data-structure-with-example","tag-queue-using-array-in-c","tag-write-a-c-program-to-implement-queue-using-array"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26878","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26878"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26878\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26878"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26878"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26878"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}