Queue

  1. ** Basic Queue Video
  2. *** Java Queue methods
     The offer method inserts an element if possible, otherwise returning false. This differs from the Collection.add method, which can fail to add an element only by throwing an unchecked exception. The offer method is designed for use when failure is a normal, rather than exceptional occurrence, for example, in fixed-capacity (or “bounded”) queues.
    The remove() and poll() methods remove and return the head of the queue. Exactly which element is removed from the queue is a function of the queue’s ordering policy, which differs from implementation to implementation. The remove() and poll() methods differ only in their behavior when the queue is empty: the remove() method throws an exception, while the poll() method returns null. NoSuchElementException is thrown by remove() if we try to remove element from an empty queue.
    The element() and peek() methods return, but do not remove, the head of the queue.
     isEmpty() to check if queue is empty. It returns boolean. 
  3. ** Circular Queue implementation using Queue Code
     This is pretty straight forward. You should know what’s the problem with non-circular array implementation of queue using Array. Just need to use the module properly. Need to keep a size variable to maintain the check that the array is not full. We can’t use the front and end variable as the array is circular.
  4. *** Queue using Linked List –How to use Queue with Linked List  Implementation Code. This is pretty straight forward. We just need to create a Linked List class will be used as out node. In our Queue class we will need to maintain front and rear(which will be reference to the Linked List Node created to hold). Rest we just need to keep maintaining these front and end as and when we queue and dequeue nodes from the queue. Handle the case of empty queue(when both front and rear are null).
  5. ***  Code – Implement Queue using Stacks (using 2 stack)
    We create two stack, s1 and s2. s1 is the one where all queue operation happen. When we need to dequeue, we move all s1 item to s2 and pop from s2, until s2 is empty. This will have a FIFO effect. Now we keep popping from s2(for every dequeue op) until it’s empty and meanwhile all push op will be in s1.  When s2 is empty and another dequeue op is needed we pop all s1 to s2.
  6. ***  Implement Stack using Queue –
      Using One Queue  – when we queue an element to the queue we dequeue all the other element one by one and enqueue them, remove the element and enqueue it and then do the same with the next element. This happens in a loop size -1 time, this will cause the last element added to get to the front of the queue.
    We do this for every element that’s added to the queue. So the pop operation will pop the last element added, LIFO like a stack.
      Using Two Queue  –  Idea is to push elements into the Queue “mainQueue” and while popping element, pop all elements except the last element one by one from “mainQueue” to temporary Queue “tempQueue”, return the last element and initialize “mainQueue” with “tempQueue”.
    One small but impactful change we do is, while copying tempQueue to mainQueue, we do not actually copy the data but initialize mainQueue = tempQueue and reinitialize the tempQueue. Basically renaming temp to main and creating a new temp.
    mainQueue = tempQueue;
    tempQueue = new LinkedList();
  7. How to efficiently implement k Queues in a single array? –
    1. divide an array and handle it
    2. [Skip] like efficiently implement k Stack in a single array?  – this will be like the dynamic solution we saw in byte-by-byte.
  8. Implement two queue in a single array – Doesn’t seems like a popular interview question as I din’t find it online. But if we had implement it we could just divide an array into two part.
    f1 = 0, r1 = -1 ,  f2 = 3, r2 = 2;  => if we had an array of size 6. Now the first queue will work smoothly(implement the circular queue logic). For the second queue we always add the 3 to the index generated before enqueue/dequeue (3 because the second queue starts from index 3 in the array).
  9. Queue Interface Another link One mORe Link   http://www.codejava.net/java-core/collections/java-queue-collection-tutorial-and-examples
  10. Reverse  a queue –
    1. Recursion
    2. using stack – in recursion we use the system stack, instead of that we will have to push to another user defined stack


  11. **** LRU Cache
  12. [Pending] Find the first circular tour that visits all petrol pumps
  13. [Pending] Given absolute unix like path simply it – SimplyPath.java

  14. [Skip] An Interesting Method to Generate Binary Numbers from 1 to n – Something very specific to Stack. No logic given but just the steps to follow. Just keep in mind that something of this sort exists. We are not solving this.
Advertisements

One thought on “Queue

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s