Menu
I have started learning Data Structures recently, and just had my own linked list implementation.
Now I stumbled upon two new data structures: stack and queue.
From what I have learned so farstack is a linked list that allows insertion / removal only from its tail, andqueue is a linked list that allows insertion only at its tail and removal only from its head.
My questions are:
Why would I use these two data structures instead of a regular linked list that allows insertion and removal from anywhere?
Also, Why are these two data structure classified as independent data structures rather than "limited access linked lists"?
330
The main difference between Stack and Linked List is that a Stack works according to the FIFO mechanism while a Linked List works by storing the data and the addresses of other nodes to refer to each other. A data structure is a way of storing data elements in computer memory.
Stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle. Queue is a container of objects (a linear collection) that are inserted and removed according to the first-in first-out (FIFO) principle.
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.
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.
172
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
