### Stacks

#### What Is Stack?

A **stack** is a data structure in which we can only access the element that was added last, and this access follows **last-in-first-out (LIFO)** principle. Stacks, for instance, can be used to implement a redo and undo function, and a backtracking algorithm (such as depth-first search, DFS).

#### Implementations

Stacks typically support the following operations.

**pop**: Remove the**top**element, which is the last element added.**push**: Add an element to the top of the stack.- peek: Return the top of the stack.

There are two common ways to implement a stack; using a linked list, and using an array.

In an implementation using a linked list, we can consider the head of the linked list as the top of the stack. Since inserting and removing an element at the beginning of a linked list takes constant time, the time complexity of the operations over stacks is also constant, \(O(1)\).

What about using an array? The time complexity depends on its implementation. If the beginning of an array represents the top of the stack, in order to push new element, we have to shift all the existing elements in the array, which would take \(O(n)\). On the other hand, if the end of the array is the top, a push operation doesn’t involve any shifting, though. Consequently, its time complexity is constant, \(O(1)\).

### Queues

#### What Is Queue?

A **queue** is a data structure in which we can only retrieve its elements in the same order that they are added, which follows **first-in-first-out (FIFO)** principle. Queues are commonly used to implement a cache, and a breadth-first search.

#### Implementations

Queues typically support the following operations:

**dequeue**: Remove the**top**element, which is the oldest element.**enqueue**: Add a new element at the end of the queue.- peek: Return the top of the queue.

Queues can also be implemented using either an array or a linked list. When using a singly linked list with a tail pointer, and considering the head of the linked list as the top of the stack, the time complexity of each operation is \(O(1)\).

### Reference

- Gayle Laakmann McDowell. (2015). Cracking the Coding Interview: 189 Programming Questions and Solutions (6th ed.). CareerCup.
- (What are stacks?) https://www.youtube.com/watch?v=KcT3aVgrrpU
- (What are queues?) https://www.youtube.com/watch?v=D6gu-_tmEpQ
- (Stack implementations using arrays and linked lists) https://medium.com/@kaichimomose/stack-implementation-and-complexity-c176924e6a6b
- (Implementations of stacks and queues, and their time complexities)

https://stackoverflow.com/a/7477556