Stacks & Queues
Stack is a Last-In-First-Out ( LIFO ) type data structure i.e the element which is added first will be removed last. Stack supports only two operations : PUSH ( inserting an element on the top of stack ) and POP ( removing the top element from stack ).
Queue is a First-In-First-Out ( FIFO ) type data structure i.e the element which is added first will be removed first. Queue also supports two operations : ENQUEUE ( inserting an element at the rear end of the queue ) and DEQUEUE ( removing an element from the front end of the queue ).
Circular Queue is the most common practical implementation of the queue data structure. If the queue size is limited ( when array based implementation is used ), we can insert elements towards the beginning of the queue
( if there is space ) when we reach the maximum limit at the rear end.
Both Stack and Queue can be implemented using arrays or linked lists. Following figure gives a rough visualization of the stack and queue data structures :
Now, let’s see some problems based on stacks and queues. Initially, we will see how to implement stack, queue and circular queue using arrays and then move on to some general problems where stacks and queues are used. The standard template library ( STL ) of C++ has an inbuilt implementation of stack and queue.