Intro to competitive programming - 2

Covered in this section:

• Important Data structures like Queue and stack
• Important problems related to Queue and stack

Stack

Stack is a linear data structure used to store elements. It follows LIFO (Last-in-First-out) principle. It is reminiscent of literal "stacks" in the real world.

C++ STL related to stack includes:

• push(): is used for adding an element to the top of stack.
• top(): used to extract information of the topmost (most recent) element of the stack.
• pop(): used to remove the top most element of stack.
• empty(): Returns true if the stack is empty and returns false when stack has elements.

Queue

is also a linear data structure like stack. However, unlike stack, it follows FIFO (First-in-First-out) principle. It is reminiscent of literal "queues" in the real world.

C++ STL related to queues:

• push(): Adds an element to the end of the queue.
• pop(): Removes the front element of the queue.
• empty(): Returns true queue is empty, otherwise returns false.
• front(): Returns a reference to the first (front) element of the queue without removing it.
• back(): Returns a reference to the last (back) element of the queue without removing it.

Deque (Double ended queue)

is like queue data structure except it supports operations like that of queue at both ends with same time complexity. C++ STL related to deque includes:

• push_back(): Adds an element to the end (back) of the deque.
• push_front(): Inserts an element at the beginning (front) of the deque.
• pop_back(): Removes the last (back) element of the deque.
• pop_front(): Removes the first (front) element of the deque.

Important problems

Brackets / parenthesis matching

This GFG article sums up the problem and its soln well. Its often asked in technical interviews and uses Stack data structure.

In, Post, Pre - fix calculators

Priority order of operators: ^ (power) => [/ (division) and * (multiplication)] => [+ (Addn) and - (substraction)] [BODMAS rule]. This YT video is a good resource for understanding the calculator types. This YT video explains Shunting yard algorithm. Try to implement it and test with testcase: 4*(1+2*(9/3)-5) ans: 41293/*+5-*.

post fix calculator:
we start with an empty stack and rad expression from left to right. when we encounter an operand, we pop 2 elements from stack and do operation and pop the number we got back into the stack.