Stacks, queues and linked lists
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 far
stack is a linked list that allows insertion / removal only from its tail, and
queue 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"?
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.
- Iterating over a data structure with 51 million primes quickly
- Radix(Trie) Tree implementation for Customer search in Java
- Big Number Subtraction in C
- Difference between back tracking and dynamic programming
- Javascript data structures library
- Longest Subarray with Maximum Bitwise AND
- Cast/Convert tree structure to different type
- Allocate bikes to people - First Priority (Closest bike to closest person)
- How to merge 3 sorted arrays into 1 sorted array in Big-O(N) time?
- Split a binary search Tree
- Suffix tree VS Tries - in plain English , what's the difference?
- Does a standard implementation of a Circular List exist for C++?
- Simplest code for array intersection in javascript
- Adding DP to 0/1 knapsack
- Efficient Interval Storage Using C++ Standard Library
- Tree data structure in C#
- Insert after specific element in LinkedList java
- Optimal solution for the "celebrity" algorithm
- Finding the K-th largest element using heap
- How to repeatedly insert elements into a sorted list fast
- Delete method of binary search tree delete all nodes instead of only the selected one C++
- What would a "frozen dict" be?
- Understanding the Need for Generator Functions in JavaScript
- most stones removed with same row or column
- How to pass an object to a constructor where the former becomes part of the instance's data and its getters can reach class specific props and methods
- What is the intuition behind the Fibonacci heap data structure?
- What does it mean for a data structure to be "intrusive"?
- Data Structure and Algorithm for a 3D Volume?
- How can I trigger an expensive computation at most once every 30 minutes?
- Definition of C# data structures and algorithms