Explanation of the Stack Data Structure
Concept of a Stack
- A stack means a pile of things.
- It is a LIFO(Last In First Out) data structure where data can be inserted and removed only from one end.
- The most recently added data is removed first.
Structure of a Stack
- Top of stack: top
- Bottom of stack: not needed
- Element, item
- Insert/delete operations
Stack Operations
A stack follows LIFO(Last In First Out). In other words, the item most recently added to the stack is the first item to be removed.
- push(x): adds the given element x to the top of the stack.
- pop(): if the stack is not empty, removes and returns the top element.
- isEmpty(): returns true if the stack is empty, otherwise false.
- peek(): if the stack is not empty, returns the top element without removing it.
- isFull(): returns true if the stack is full, otherwise false.
- size(): returns the number of all elements in the stack.
- display(): outputs all elements in the stack.
Uses of a Stack
- Function calls
- Stacks are useful when using recursive algorithms.
- Recursive algorithms
- When functions must be called recursively, temporary data is pushed onto the stack.
- When returning from recursive functions and performing backtracking, the temporary data pushed onto the stack must be popped.
- A stack makes this sequence of actions intuitive.
- A stack also makes it possible to implement recursive algorithms in an iterative form.
- Recursive algorithms
- Web browser history(back button)
- Undo
- Creating reversed strings
- Checking parentheses in expressions(parentheses checks for operator precedence)
- Example: determining a Valid Parenthesis String(VPS)
- Calculators(postfix notation calculation)
