Stacks and Queues
For keep your self and people, these days we should keep minimum 1 meters away from them to reduce the risk of Coronavirus spreading, So not is bad that to talk about types of a fundamental Data type.
a Stack is an abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the most recently added element that was not yet removed.
The order may be LIFO(Last In First Out) or FILO(First In Last Out).
a Queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence.
The order is First In First Out (FIFO).
Queue with Linked List
In simply put, We have two pointers and maintain one pointer to first and one in last nodes in a linked list.
We have two critical methods, DeQueue(This operation adds a new node after last and moves last to the next node) and EnQueue(This operation removes the front node and moves front to the next node).
Let me show to you a simple code of the implementation of Queue :
Blow code is a linked list node that maintains a Queue entry.
A class to represent a linear collection that as I told before it has First in First Out (fifo) semantics queue is commonly implemented with a Linked List algorithm that keeps track of Two elements.
And you can implement Queue with Array that sample of this is accessible in my GitHub.
Stack with Linked List
As I told before, Stack is a linear collection which has last in first out (lifo) semantics elements are being added to the top of the stack and get removed from top as well.
In simply put, We have One pointer and maintain one pointer to top in a linked list.
We have three critical methods, Push(Insert the element into linked list),Pop( Return top element from the Stack and move the top pointer to out) and Peek(return the top element).
Let me show to you a simple code of the implementation of Stack :
And you can implement Stack with Array that sample of this is accessible in my GitHub.
One of the big benefits of Stack is, You can use an explicit stack to remove Recursion.
Resources: Algorithms Robert Sedgewick