Stacks

Stacks are an ordered data structure where the order is first in last out. You can basically imagine it as stacking plates. The first plate you put down is on the bottom but when you get a plate you take it from the top.

https://en.wikipedia.org/wiki/Stack_(abstract_data_type)#/media/File:Lifo_stack.png

Since you always insert and retrieve from the top the run time for both options is O(1). The pop method is removing the top value from the stack which would also be O(1). You would normally only be able to see the top value and to see the rest you would have to have to pop the top. The space needed would be O(n) which is the size of whatever you will push into the stack.

Stacks are a recursive data structure where you would only be able to see the head or the top of the stack. Whenever you pop the stack the new head will be the data directly below or next to the previous top. Stacks can be implemented in different ways including arrays and lists.

Some applications of using stacks include:

• Backtracking — Like solving a maze. Pushing into the stack every step taken and when you reach a dead end you would pop it until you can take a different direction.
• Expression Evaluation — Solving mathematical expressions following order of operations rule.
• Syntax Parsing — Many compilers use stacks for parsing expressions and program blocks before translating into low level code.
• Parenthesis Checking — Checking if open parenthesis matches closing parenthesis and if it is valid
• Function Call — Keeps track of information about active functions and subroutines