Difference between FIFO and LIFO
FIFO stands for First in First Out. It is nothing but a queue in which the item that enters first, leaves before any other does. We can encounter queues in many real life situations such as movie ticket counter, vehicles stopped on a traffic signal and so on. LIFO on the other hand stands for Last in First Out. It is also called a stack. A pile of books can be seen as a stack. We can see many applications of stacks in our daily lives. For example, the back button on your browser which takes you to previously opened links is but a simple application of a stack.
Implementation
The implementation of stacks can be achieved by simply using an array and a variable that keeps track of the top of the stack. This variable is generally called “tos” (top of stack) and is initiated with a value -1 and is incremented every time a new entry comes into stack. This operation is called a “push” operation. Opposite to push is “pop”. A queue is also implemented with an array however in this case two variables called “rear” and “front” keep track of the queue. Every time a new value is added in a queue a “rear” is incremented. On retrieval from the queue a “front” is implemented.
Modifications
Various modifications are possible in cases of queues. One of the most popular is Priority Queue. In this case, some items are assigned with higher priority than others and even above the item that should be removed as per the rules. Another modification is circular queue in which rear and front are joined. The problems of overflow can be dealt with to some extent by using such modifications. Priority can also be assigned to items in the stack that are required to be popped earlier than others.
Uses
FIFO or queue has various applications in computer science one of which is Disk Scheduling. A disc controller receives the input/output requests in a queue and schedules the disc traversal accordingly. Same is the case with processors. The computation requests from different applications are stored in a queue. Queues can also be seen in electronics communication with switches, routers and bridges. Stacks on the other hand are extremely important and the most basic data structures used in computer science. Internal recursion, a function for calling and restoring capabilities would not have been possible without the use of stacks. Stacks are also used to store the current state of a system, in case of interruptions.
Similarities and Differences
LIFO/Stack
- Last In First Out
- Implemented using an array and a variable (tos) that keeps track of the top of stack.
- POP and PUSH operations.
- Recursion and function calling are implemented with the help of stacks in internal memory.
FIFO/Queue
- First In First Out
- Two variables called “rear” and “front” keep the track of queue.
- Circular Queue and priority queue are modifications of simple queue.
- FIFO is used by controllers in Disk scheduling.
- Switches, routers and bridges also use queues communication networks to temporarily store or buffer the packets.
