Computer Science · Ch 3 — Stack
Summary
Summary
- Stack is a data structure in which insertion and deletion is done from one end only, usually referred to as TOP.
- Stack follows the LIFO principle, using which an element inserted last will be the first one to be out.
- PUSH and POP are two basic operations performed on a stack for insertion and deletion of elements, respectively.
- Trying to pop an element from an empty stack results in a special condition called underflow.
- In Python, a
listis used for implementing a stack, and its built-in functionsappend()andpop()are used for insertion and deletion, respectively. Hence, no explicit declaration of TOP is needed. - Any arithmetic expression can be represented in any of the three notations: Infix, Prefix, and Postfix.
- While programming, Infix notation is used for writing an expression in which binary operators are written in between the operands.
- A single traversal from left to right of a Prefix/Postfix expression is sufficient to evaluate the expression, as operators are already correctly placed as per their order of precedence.
- A stack is a commonly used data structure to convert an Infix expression into its equivalent Prefix/Postfix notation. …