The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

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 :

Stack and Queue

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.

Back | Next

All problems on Stacks and Queues
* Implement a stack using an array
* Implement a queue using an array
* Implement a circular queue using an array
* Design and implement an extended stack using linked list which permits push, pop & maxElement (gets maximum element in the stack) in O(1) time complexity
* Implement a circular queue using linked list
* Implement a Queue data structure using two stacks
* Sort a Queue using two stacks
* Convert infix expression to the postfix notation
* Implement an algorithm to evaluate a postfix expression
* Given a stack with only 0s & 1s, find the majority element in the stack
* Implement an inplace algorithm to sort a stack