際際滷

際際滷Share a Scribd company logo

Unit-ii-Queue ADT.pptx

Download as PPTX, PDF
M
Mano Arun

A queue is a list where insertion occurs at one end and deletion occurs at the other end, following a first-in first-out (FIFO) policy. There are two basic queue operations: enqueue adds an item to the back of the queue, and dequeue removes an item from the front. Queues can be implemented using arrays, with front and rear pointers, or linked lists. For arrays, enqueue increments the rear pointer and adds to the rear, while dequeue accesses the front and increments front. Linked lists add to the head for enqueue and remove from the tail for dequeue.

1 of 14
Download to read offline
Queue
6/4/2023 CS 201 What is a Queue? Like stacks, queues are lists. With a queue, however, insertion is done at one end whereas deletion is done at the other end. Queues implement the FIFO (first-in first-out) policy. E.g., a printer/job queue! Two basic operations of queues: dequeue: remove an item/element from front enqueue: add an item/element at the back dequeue enqueue
6/4/2023 CS 201 Implementation of Queue (Array) use Array with front and rear pointers as implementation of queue Queue arr 0 1 7 8 9 2 3 4 5 6 A B C D E F G front rear
Enqueue Operation Queues maintain two data pointers, front and rear. The following steps should be taken to enqueue (insert) data into a queue Step 1 Check if the queue is full. Step 2 If the queue is full, produce overflow error and exit. Step 3 If the queue is not full, increment rear pointer to point the next empty space. Step 4 Add data element to the queue location, where the rear is pointing. Step 5 return success.
Unit-ii-Queue ADT.pptx
procedure enqueue(data) if queue is full return overflow endif rear rear + 1 queue[rear] data return true end procedure
Dequeue Operation Accessing data from the queue is a process of two tasks access the data where front is pointing and remove the data after access. The following steps are taken to perform dequeue operation Step 1 Check if the queue is empty. Step 2 If the queue is empty, produce underflow error and exit. Step 3 If the queue is not empty, access the data where front is pointing. Step 4 Increment front pointer to point to the next available data element. Step 5 Return success.
Unit-ii-Queue ADT.pptx
procedure dequeue if queue is empty return underflow end if data = queue[front] front front + 1 return true end procedure
Check full bool isfull() { if(rear == MAXSIZE - 1) return true; else return false; }
Check empty bool isempty() { if(front < 0 || front > rear) return true; else return false; }
6/4/2023 CS 201 Circular Array To implement queue, it is best to view arrays as circular structure 0 1 7 8 9 2 3 4 5 6 A B C D E F G front back front back A B C D E F G 0 1 7 8 9 2 3 4 5 6 Circular view of arrays.
6/4/2023 CS 201 Implementation of Queue (Linked List) Can use LinkedListItr as underlying implementation of Queues a1 a2 a3 a4 head tail Queue lst LinkedList addTail
dequeue: remove an item/element from front ( tail pointer) - Delete first enqueue: add an item/element at the rear ( head pointer) insert first

More Related Content

Unit-ii-Queue ADT.pptx

  • 2. 6/4/2023 CS 201 What is a Queue? Like stacks, queues are lists. With a queue, however, insertion is done at one end whereas deletion is done at the other end. Queues implement the FIFO (first-in first-out) policy. E.g., a printer/job queue! Two basic operations of queues: dequeue: remove an item/element from front enqueue: add an item/element at the back dequeue enqueue
  • 3. 6/4/2023 CS 201 Implementation of Queue (Array) use Array with front and rear pointers as implementation of queue Queue arr 0 1 7 8 9 2 3 4 5 6 A B C D E F G front rear
  • 4. Enqueue Operation Queues maintain two data pointers, front and rear. The following steps should be taken to enqueue (insert) data into a queue Step 1 Check if the queue is full. Step 2 If the queue is full, produce overflow error and exit. Step 3 If the queue is not full, increment rear pointer to point the next empty space. Step 4 Add data element to the queue location, where the rear is pointing. Step 5 return success.
  • 6. procedure enqueue(data) if queue is full return overflow endif rear rear + 1 queue[rear] data return true end procedure
  • 7. Dequeue Operation Accessing data from the queue is a process of two tasks access the data where front is pointing and remove the data after access. The following steps are taken to perform dequeue operation Step 1 Check if the queue is empty. Step 2 If the queue is empty, produce underflow error and exit. Step 3 If the queue is not empty, access the data where front is pointing. Step 4 Increment front pointer to point to the next available data element. Step 5 Return success.
  • 9. procedure dequeue if queue is empty return underflow end if data = queue[front] front front + 1 return true end procedure
  • 10. Check full bool isfull() { if(rear == MAXSIZE - 1) return true; else return false; }
  • 11. Check empty bool isempty() { if(front < 0 || front > rear) return true; else return false; }
  • 12. 6/4/2023 CS 201 Circular Array To implement queue, it is best to view arrays as circular structure 0 1 7 8 9 2 3 4 5 6 A B C D E F G front back front back A B C D E F G 0 1 7 8 9 2 3 4 5 6 Circular view of arrays.
  • 13. 6/4/2023 CS 201 Implementation of Queue (Linked List) Can use LinkedListItr as underlying implementation of Queues a1 a2 a3 a4 head tail Queue lst LinkedList addTail
  • 14. dequeue: remove an item/element from front ( tail pointer) - Delete first enqueue: add an item/element at the rear ( head pointer) insert first