Last Updated on September 22, 2023 by Prepbytes
In this article, we will learn what is a stack, the algorithm for the implementation of stack using array, the algorithm of the stack with an example dry-run, the program for the implementation of stack using array, and the applications of stack.
What is a Stack in Data Structures?
A stack represents a sequential arrangement of data, adhering to the last in, first out (LIFO) principle. Implementing the stack data structure requires a pointer known as "top." This top pointer is essential as it indicates the most recently added element, ensuring that the last inserted element can be retrieved.
What is LIFO (Last In First Out) Strategy?
Following the last in, first out (LIFO) approach, the element that has been inserted most recently is the first to be extracted. An apt illustration of this principle can be observed with a stack of dinner plates. In this scenario, the uppermost plate is retrieved initially, followed by a sequential removal of the plates beneath it. This practical instance serves as a real-life demonstration of a stack.
Algorithm for the Implementation of Stack using Array
Push: This function is used to insert a new element into the stack
Algorithm to perform Push Operation:
- if the stack is full then return
- else increment the value of the top pointer
- assign the new value to stack[top]
Pop: This function is used to retrieve a topmost element from the stack
Algorithm to perform Pop Operation:
- if the stack is empty then return
- else store the value of stack[top]
- decrement the value of the top pointer
- Return the stored value
Top: This function is used to get the top element from the stack.
Algorithm to perform Top Operation:
- if the stack is empty then return
- else return stack[top]
isEmpty: This function is used to check whether the stack is empty or not.
Algorithm to Perform isEmpty Operation:
- if the top is greater than 1 then return true
- else return false
Algorithm of the Stack with an example dry-run
Now, we know what is stack and the algorithms of operations of the stack. Let’s understand the implementation of stack using array with an example dry run.
First, we will take an empty array of capacity 5 and initialize a top variable with -1.
Now, let’s perform various operations to understand the working of the stack.
Operation: push(10)
In this push operation, first, we will check if the stack is full or not. If the stack is full we will not do anything. If the stack is not full then we will increment the variable top by 1. In this case, the stack is empty so we will increment the top by 1 and the top will become 0. Now, we will assign value 10 to stack[top].
Operation: push(20)
In this push operation, we will insert new element 20 at the top of the stack. The stack is empty so we will increment the top by 1 and the top will become 1. Now, we will assign value 20 to stack[top].
Operation: pop()
In this pop operation, first, we will check if the stack is empty or not. If the stack is empty we will not do anything. If the stack is not empty then we will store the value of stack[top] (20) in the temp variable. After that, we will decrement the value of the top by 1 so the top will become 0 and remove the top element from the array.
Operation: push(30)
In this push operation, we will insert new element 30 at the top of the stack. The stack is empty so we will increment the top by 1 and the top will become 1. Now, we will assign the value 30 to stack[top].
Operation: push(40)
In this push operation, we will insert new element 40 at the top of the stack. The stack is empty so we will increment the top by 1 and the top will become 2. Now, we will assign the value 40 to stack[top].
Operation: push(50)
In this push operation, we will insert new element 50 at the top of the stack. The stack is empty so we will increment the top by 1 and the top will become 3. Now, we will assign the value 50 to stack[top].
Operation: pop()
In this pop operation, first, we will check if the stack is empty or not. If the stack is empty we will not do anything. If the stack is not empty then we will store the value of stack[top] (50) in the temp variable. After that, we will decrement the value of the top by 1 so the top will become 2 and remove the top element from the array.
Program for the Implementation of Stack using Array
Let’s see how to write a program for the implementation of stack using array.
// java program for implementation of stack using array
class Stack {
static final int capacity = 5;
int top;
int a[] = new int[capacity]; // Maximum size of Stack
boolean isEmpty()
{
return (top < 0);
}
Stack()
{
top = -1;
}
boolean push(int x)
{
if (top >= (capacity - 1)) {
System.out.println("Stack is full");
return false;
}
else {
a[++top] = x;
System.out.println(x + " is pushed into the stack");
return true;
}
}
int pop()
{
if (top < 0) {
System.out.println("Stack empty");
return 0;
}
else {
int x = a[top--];
return x;
}
}
int peek()
{
if (top < 0) {
System.out.println("Stack empty");
return 0;
}
else {
int x = a[top];
return x;
}
}
void print_stack(){
System.out.print("Stack: ");
for(int i = top;i>-1;i--){
System.out.print(" | "+ a[i]);
}
System.out.print(" |");
System.out.println("");
}
}
class Main {
public static void main(String args[])
{
Stack s = new Stack();
s.push(10);
s.print_stack();
s.push(20);
s.print_stack();
System.out.println(s.pop() + " is popped from the stack");
s.print_stack();
s.push(30);
s.print_stack();
s.push(40);
s.print_stack();
s.push(50);
s.print_stack();
System.out.println(s.pop() + " is popped from the stack");
s.print_stack();
}
}
Output:
10 is pushed into the stack
Stack: | 10 |
20 is pushed into the stack
Stack: | 20 | 10 |
20 is popped from the stack
Stack: | 10 |
30 is pushed into the stack
Stack: | 30 | 10 |
40 is pushed into the stack
Stack: | 40 | 30 | 10 |
50 is pushed into the stack
Stack: | 50 | 40 | 30 | 10 |
50 is popped from the stack
Stack: | 40 | 30 | 10 |Applications of Stack Data Structure:
The stack data structure finds practical applications in various domains due to its Last In First Out (LIFO) nature. Some key applications include:
- Function Calls and Recursion: Stacks are vital for managing function calls and recursive operations in programming languages. They enable keeping track of execution contexts and ensuring proper return values.
- Expression Evaluation: Stacks are employed in parsing and evaluating arithmetic expressions. They help convert infix expressions to postfix (or prefix) form, simplifying calculations.
- Undo and Redo Operations: Stacks are valuable for implementing undo and redo functionalities in applications. Each operation is pushed onto the stack, enabling easy reversal of actions.
- Browser History: Stacks can be used to maintain the history of visited web pages in a browser, enabling the user to navigate back and forth.
- Backtracking Algorithms: Stacks are crucial for backtracking algorithms in search and optimization problems, enabling the exploration of multiple paths and subsequent backtracking when necessary.
- Memory Management: Stacks play a role in memory management by allocating and deallocating memory for function calls and local variables.
- Compiler and Interpreter Design: Stacks are used to evaluate expressions, manage symbols, and store intermediate results during the compilation and interpretation of programming languages.
Conclusion
In conclusion, understanding the implementation of a stack using an array is crucial for grasping the fundamentals of data structures and their applications. This approach offers a straightforward means of organizing and managing data using the Last In First Out (LIFO) principle. The array-based implementation provides an efficient and predictable way to perform stack operations, enabling various practical applications in programming and beyond.
Frequently Asked Questions (FAQs) about Implementation of Stack using Array
Below are some FAQs related to Implementation of Stack using array:
1. What is an array-based implementation of a stack?
An array-based implementation of a stack involves using an array data structure to store elements in a sequential manner, adhering to the Last In First Out (LIFO) principle.
2. How does the array-based stack work?
Elements are added (pushed) to the top of the array and removed (popped) from the same position. The top position is managed by an index that tracks the current top element.
3. What is the advantage of implementing a stack using an array?
Array-based implementation of stacks is memory-efficient and offers constant-time complexity for basic operations like push and pop.
4. What are the disadvantages of using an array for a stack?
The size of the array is fixed, which can lead to limitations in terms of memory usage. Dynamic resizing might be required if the stack grows beyond the initial array size.
5. How is the initial size of the array determined in stack implementation?
The initial size is usually chosen based on the expected usage of the stack. It’s important to strike a balance between memory usage and the potential need for resizing.
6. Can the array-based stack implementation lead to stack overflow?
Yes, if the number of elements added to the stack exceeds the size of the array, it can lead to a stack overflow error.
7. How is the size of the stack managed in the array-based implementation?
The size of the stack is controlled by the size of the underlying array. If the stack grows beyond this size, dynamic resizing or other mechanisms are needed.