Both stacks and queues are abstract data types that can store items in an order. However, the principal or the basic differences between them are the order of elements and their operations: addition (push/enqueue) and removal (pop/dequeue).
**Stack**: A stack is a linear data structure which follows a particular order in which the operations are performed. The order may be Last In First Out (LIFO) or First In Last Out (FILO).
The main operations associated with stack are:
- Push: Adds an element to the stack. If the stack is full, it results in an Overflow condition.
- Pop: Removes an element from the stack. The items are popped in the reverse order in which they are pushed. If the stack is empty, it results in an Underflow condition.
Here’s a mathematical notion of a stack with push and pop operations. Let s be a stack and x be an element, then:
1. push(s, x) inserts x at the top of stack s.
2. pop(s) removes the top most element from the stack s.
There are many real-life examples of a stack. Consider a stack of plates, where the plate at the top is the first one to be removed, i.e., the plate that was pushed last is popped first.
**Queue**: A queue is a linear data structure that stores elements in a sequential manner, following a First-In-First-Out (FIFO) rule. This means that the item that is added (enqueued) first, is the first one to be removed (dequeued).
The primary operations associated with queue are:
- Enqueue: Adds an element to the end of the queue.
- Dequeue: Removes an element from the front of the queue.
Here’s a mathematical notion of a queue with enqueue and dequeue operations. Let q be a queue and x be an element, then:
1. enqueue(q, x) adds x at the end of queue q.
2. dequeue(q) removes the first element from the queue q.
As an example, the queue in a supermarket is the best example of a queue, where the person who comes first is served first (the person is removed from the queue).
In summary, the primary distinguishing characteristic of stacks and queues are their rules for element access (item removal): stacks are LIFO/FILO while queues are FIFO.