Stacks, queues and linked lists

Stacks and queues have their own reason of existence. A stack is a FILO (First In Last Out) or LIFO (either ways) data structure that could be implemented using arrays, linked lists or other forms. Consider browser history. You navigate to Site A -> then B -> then C -> D. As a user moves ahead, you first push (insert at tail) the list of websites. This ensures that the current site is always at the top of the stack. Stack in action

Then when the user hits back button, you pop the one at the top (removing from tail - the same end used for insertion) which gives the last visited site - C. Thus the concept of First In (which was Site A) and Last Out (the last one to go in was Site D which in turn became the first one to go out)

Similar could be said for queue which is FIFO (First In First Out). Consider the example of job queue. When performing a job, you would (not considering any optimization algorithms) serve the one first to arrive. This makes queue an excellent data structure to process jobs on a first come first serve basis.

In both the cases, you wouldn't want an arbitrary removal or insertion of elements at any index. No, that would result in an undesirable behaviour. Hence, the need for stack/queue. I would again emphasize that stacks/queues can be implemented by enforcing restrictions on linked lists.

Sorry for the poor image quality - I just drew it in paint.


Stack is basically a data structure that follows LIFO (LAST IN FIRST OUT). Queue is one which follows FIFO (FIRST IN FIRST OUT).

In general, Stacks and Queues can be implemented using Arrays and Linked Lists.

The reason you would use Linked List for implementing Stack is when you need a functionality involving LAST IN FIRST OUT form and you are not sure how many elements that functionality requires. So you would use LinkedList creating nodes dynamically depending on the requirement.

Same goes for Queues

The reason both are independent is because both follow different principles i.e LIFO and FIFO respectively.