LeetCode

A queue follows FIFO (first in first out). In a queue, elements are added and removed from opposite sides.

• There is also a data structure called a deque, short for double-ended queue, and pronounced “deck”. In a deque, you can add or delete elements from both ends.

Adding to a queue is called enqueue and deletions are called dequeue.

A doubly linked list that maintains pointers to the head and tail (both ends, usually with sentinel nodes) can implement an efficient queue.

A stack is an ordered collection of elements where elements are only added and removed from the same end. Another term used to describe stacks is LIFO, which stands for last in, first out.

The characteristic that makes something a “stack” is that you can only add and remove elements from the same end. It doesn’t matter how you implement it, a “stack” is just an abstract interface.

Stacks and recursion are very similar. This is because recursion is actually done using a stack. Function calls are pushed on a stack. The call at the top of the stack at any given moment is the “active” call. On a return statement or the end of the function being reached, the current call is popped off the stack.

Recursion is a problem solving method. In code, recursion is implemented using a function that calls itself.

Any iterative algorithm can be written recursively.

Iterative algorithms use for loops and while loops to simulate repetition. Recursive algorithms use function calls to simulate the same logic.

Base cases are conditions at the start of recursive functions that terminate the calls.

• Think from one level above the base case. Think from leaf node’s perspective.

Where recursion shines is when you use it to break down a problem into “subproblems”, whose solutions can then be combined to solve the original problem.

1.4 Analysis of Algorithms, LeetCode’s Interview Crash Course: Data Structures and Algorithms