Skip to main content

Stacks and Queues

Stack#

It is time to learn about some more basic data structures that have a wide range of application. Stack is a data structure that follows the LIFO or Last In First Out principle. You would find the use of stack extremely critical to solving some problems which otherwise would have become a nightmare, so before you are ready to use it, first learn about it.

Caution

The following STL utilities for Stack in C++ are a must know : empty(), size(), pop(), push(), top().

Try It Yourself#

Can you implement basic Stack operations using linked list? What is the time complexity of the basic operations in your implementation?

Queue#

Queue is another useful and a must know data structure, that you will be applying in several other algorithms that you will study later, so it is important that you have a clear cut understanding of the First In First Out principle of queue and its basic operations.

Caution

The following STL utilities for Queue in C++ are a must know : empty(), size(), pop(), push(), top().

Try It Yourself#

Can you implement basic Queue operations using linked list? What is the time complexity of the basic operations in your implementation?

Dequeue#

Dequeue comes as a variation to Queue, compared to Queue which is single ended meaning that elements can be pushed only from the back, Dequeue is designed to allow pushing of elements both from the front and from the back, this speciality of dequeue can be utilised in solving some tricky questions, but first learn in depth about it.

Caution

The following STL utilities for Deque in C++ are a must know : empty(), size(), front(), back(), pop_back(), push_back(), pop_front(), push_front().

Minimum Stack / Minimum Queue#

Variety comes with everything even with Stack and Queue, here are other useful variations. Knowing these would definitely come in handy, so what are you waiting for, aren’t you a little bit curious.

QUESTION