Stack & Queues

Stacks:-

Analogy to stack is --> as you keep getting the letters, you keep putting them one over the another. This is called stacking.It follows the principle "Last in first out".

Underlying data structure can be array. Important methods of a stack are :-

1) Push --> to add something
2) Pop --> To remove something
3) Peek --> Get the top most element
4) isEmpty
5) isFull

In java we have a class -- Stack which can perform these operations and also has one more method called search (Object o)

Error Handling :- we need to take care of error handling when dealing with push() and pop() method as they can throw exception. Push when stack is full and pop when stack is empty.

Efficiency :- O(1) as one item is poped and pushed at a time.

Queues:- (We will discuss this in terms of Java API)

Analogy to queue is --> We can think of queue as line of people standing at some register to buy something.Queue is more of a British word I guess. It follows the principle of FIFO -- "First In First Out".

To visualize queue in form of an array, as items start inserting, index 0 will be the head of the queue in this case and say we insert insert 10 items, so in that case index 9 will be tail.

To add a new item we will simply one more item to the array and tail pointer will move to index 10

To remove a item, it has to be removed from head only to follow the queue principal for FIFO. Sp if we remove an item from queue, head pointer will move to index 1

Circular Queue :-

Now if we continue the above process of addition & removal from the queue, then in that case, a situation will come when tail will reach end of the array and head of the array also move up in the array after few deletions, then in that case tail pointer can go to index 0 and head will continue to be where it was. After few deletions and insertion, head can again come back behind tail in the array and this process will continue and utilize the array space in best possible way. We can this kind of queue as circular queue.

Priority Queue:-

In priority queue, we insert items in a queue in specific order such that say --> say largest number always remain at the rear and smallest number always remain at the front.

There is a better way to implement priority queue using heap sort.

Efficiency of priority queue:-

Insertion --> O(N)
Deletion --> O(1)




Below stuff more to do with Java implementation of queue. Refer other links.


Some important points to remember:-

1) A queue has a head and a tail
2) A new element is added to the tail and elements to-be processed are taken from the head as this follows the order in which elements were inserted.
3) In java implementation of Queue, they do apply duplicate insertion as it is the order in which elements are inserted which matter and not the value.

Queue interface has three child interfaces:-

1) Dequeue
2) BlockingQueue
3) BlockingDequeue and there some more which have been introduced with new java version which we are not going to discuss in this thread.




Queue can be implemented using both array and linked list.

In java, queue is an interface.  This interface has to be implemented by some underlying class:-

1) Stack :-

We can implement queue using 2 stacks. Push() or enqueue in queue is a common operation in both stack and queue as in both of them, we have to add element.

Problem comes, when we have to pop or dequeue the stack since in stack, we follow LIFO and in queue,

2) LinkedList
3) Array

For more practice stuff , we will refer this guide --> http://www.codejava.net/java-core/collections/java-queue-collection-tutorial-and-examples#WhatIsQueue