STACK DATA STRUCTURE
Definition
A stack is an ordered list in which insertion and deletion are done at one end, called top. The last element inserted is the first one to be deleted. Hence, it is called the Last in First out (LIFO) or First in Last out (FILO) list. In a stack, the order in which the data arrives is important.
A pile of plates in a cafeteria is a good example of a stack. The plates are added to the stack as they are cleaned and they are placed on the top. When a plate, is required it is taken from the top of the stack. The first plate placed on the stack is the last one to be used.
Applications
- Balancing of symbols/brackets in an expression.
- Conversion & Evaluation of infix, postfix, prefix expression(to be discussed in seperate blog posts).
- Implementing function calls (including recursion).
- Used in many algorithms like Tower of Hanoi, tree traversals, stock span problem, histogram problem.
- In Graph Algorithms like Topological Sorting and Strongly Connected Components
- Browser history.
- Matching Tags in HTML.
Standard Operations
Do refer the code available the end of this section to understand the following theory.
- Push: Insert an item at the top of the stack. If there is no place then stack is in overflow state.
- Pop: Remove the top item from the stack. If there are no elements then the stack is in underflow state.
- isEmpty: To check whether stack is empty or not.
- isFull: To check if stack is full or not.
- Peek Access the top item of the stack.
- Display Display the items in the stack.
Code file
Please open this in your pc or with a compatible app in your mobile.
C++ Implementation for STACK DATA STRUCTUREThat's it from this blog post. If you liked it then do share this blog with your friends or people who wanna get into programming world. Thank You!