What is a Stack?
A stack is an ordered list in which insertion and deletion are done at one end, called a 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.
Stack Real-World Examples
1. In below diagram, the first image shows a container is filled with balls we will try to always take a last inserted ball so it is a last in first out. The second image is a list of mail envelopes and most of the peoples will always take the topmost envelope and then second top etc.
2. 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.
Stack Operations
The following operations make a stack an Abstract Data Type.
Lets first familiar with few concepts that are used in stack implementation.
Stack Concepts
- When an element is inserted in a stack, the concept is called a push.
- When an element is removed from the stack, the concept is called pop.
- Trying to pop out an empty stack is called underflow (treat as Exception).
- Trying to push an element in a full stack is called overflow (treat as Exception).
Main stack operations
Push Operation
The process of putting a new data element onto the stack is known as a Push Operation.
Push operation involves a series of steps −
Step 1 − Checks if the stack is full.
Step 2 − If the stack is full, produces an error and exit.
Step 3 − If the stack is not full, increments top to a point next empty space.
Step 4 − Adds data element to the stack location, where the top is pointing.
Step 5 − Returns success.
If the linked list is used to implement the stack, then in step 3, we need to allocate space dynamically.
Check out source code for push operation in different Stack implementation:
- Stack Implementation using Array in Java
- Dynamic Stack Implementation using Array in Java
- Stack Implementation using Linked List in Java
- Stack Implementation using Array List
Pop Operation
Accessing the content while removing it from the stack, is known as a Pop Operation. In an array implementation of pop() operation, the data element is not actually removed, instead top is decremented to a lower position in the stack to point to the next value. But in linked-list implementation, pop() actually removes data element and deallocates memory space.
A Pop operation may involve the following steps −
Step 1 − Checks if the stack is empty.
Step 2 − If the stack is empty, produces an error and exit.
Step 3 − If the stack is not empty, accesses the data element at which top is pointing.
Step 4 − Decreases the value of top by 1.
Step 5 − Returns success.
Check out the source code for pop operation in different Stack implementation:
Auxiliary stack operations
- int top(): Returns the last inserted element without removing it.
- int size(): Returns the number of elements stored in the stack.
- int isEmptyStack(): Indicates whether any elements are stored in the stack or not.
- int isFullStack(): Indicates whether the stack is full or not.
Applications of Stack
Following are some of the applications in which stacks play an important role.
Direct applications
- Balancing of symbols
- Infix-to-postfix conversion
- Evaluation of postfix expression
- Implementing function calls (including recursion)
- Finding of spans (finding spans in stock markets, refer to Problems section)
- Page-visited history in a Web browser [Back Buttons]
- Undo sequence in a text editor
- Matching Tags in HTML and XML
Indirect applications
- Auxiliary data structure for other algorithms (Example: Tree traversal algorithms)
- Component of other data structures (Example: Simulating queues, Queues)
Implementation
There are many ways of implementing Stack; below are the commonly used methods.
Free Spring Boot Tutorial | Full In-depth Course | Learn Spring Boot in 10 Hours
Watch this course on YouTube at Spring Boot Tutorial | Fee 10 Hours Full Course