CSE 214 Computer Science II (Spring 2015)

RECITATION 6 – Queue

Objective:

  1. To work with Queue data structure
  2. Analyze the complexity of operations on the Queue

 

  1. [5 min] What is the order of complexity of enqueue and dequeue of queues implemented as the following?

             a. Array

           b. Singly linked list where the front is the head

           c. Singly linked list where the front is the tail

 

  1. [20 min] Consider the following scenario for a Queue max size=6: A queue of five passengers waiting to see an airline ticket agent.  The name of the passenger who has been waiting the longest is 'Byung' (pointed to by Front); the name of the most recent arrival is 'Juyoung' (pointed to by Rear).  Passenger 'Byung' will be the first one removed from the queue when an agent becomes available, and pointer Front will be moved to passenger 'Allan'.  Any new passengers will follow passenger ' Juyoung' in the queue, and pointer Rear will be adjusted accordingly. Write the code fragments for Queue implemented as a circular array for the following operations, also specify the complexity:

[link: http://www3.cs.stonybrook.edu/~sael/teaching/cse214/rec/Queue.java]

http://www3.cs.stonybrook.edu/~sael/teaching/cse214/rec/CircularArrayQueue.java]

  1. Request by 'Byung' and ‘Allan’ are processed
  2. New passengers ‘Seonyhoon’ and ‘Lakmi’ join to meet the airline ticket agent.
  3. Find the occupancy of the queue at any given time
  4. Check Queue status before the dequeue operation
  5. Check Queue status before the enqueue operation

 

  1. [10 min] Consider the following cases. Give answers justifying the operations carried out on data structure
  1. How many stacks are needed to implement a queue.
  2. How many queues are needed to implement a stack

 

  1. [15 min] Perform the following operations on Deque implemented using a doubly linklist. Also give the complexity.

[link: http://www3.cs.stonybrook.edu/~sael/teaching/cse214/rec/Deque.java

http://www3.cs.stonybrook.edu/~sael/teaching/cse214/rec/DoublyLinklist.java]

  1. Insert a new element at the front of the deque
  2. Remove the element at the rear of the deque