Introduction to Array Implementation of Stack
Array implementation of the stack can be defined as a mechanism through which all the stack-supported operations are implemented using an array as the primary data structure. The stack is a linear data structure based on the Last-in-first-out strategy (LIFO). This article will show how the stack is implemented using an array in java. We will see the importance and different uses of implementing an array stack. We will also provide a complete Java code example that demonstrates how to use an array to implement a stack and perform all stack operations with this array.
Some of the significant operations supported by stack are:
- Push: This operation adds an item to the stack; it will throw an exception if the stack’s capacity is full.
- Pop: This process removes the last element inserted into a stack in reverse order of their insertion; it will throw an underflow exception if the given stack is empty.
- Peek: This operation returns the topmost element of the stack.
- IsEmpty: Checks if a stack is empty or not. Returns true if the given stack is empty; otherwise, it returns false.
- IsStackFull: Checks if a stack is full or not. Returns true if the given stack is full; otherwise, it returns false.
Uses of Array Implementation of Stack
The major applications of using an array-based implementation of the stack are as follows:
- Undo operation in text files or other text editors like notepad++ takes place using the stack as an underlying data structure.
- The problem of reversing a word can be solved using a stack.
- Java Virtual machine uses a stack to store method calls and implement recursion.
- The compiler uses a stack to achieve syntax checking.
- You can use a stack in backtracking algorithms.
The stack’s widespread applications make it one of computer science’s most commonly used data structures.
Importance of Using Array Implementation of Stack
Using an array to implement a stack has a significant advantage over using a linked list because it is more time-efficient. With a linked list, allocating pointers of nodes whenever there is a change in the stack size requires extra time. All operations in an array-based stack implementation have a time complexity of O(1).
Example:
Here is a java code example showing how a stack is implemented using an array in java.
package com.edubca.stack.arraydemo;
public class StackArrayImpl {
int size;
int arr[];
int topElement;
// constructor having size as parameter
StackArrayImpl(int size) {
this.size = size;
this.arr = new int[size];
this.topElement = -1;
}
// this method inserts an element on stack
public void push(int element) {
if (!isStackFull()) {
topElement++;
arr[topElement] = element;
System.out.println("Element Pushed on Stack is :" + element);
} else {
System.out.println ("Cannot insert Stack is full...");
}
}
// this method deletes an element from stack
public int pop() {
if (!isEmpty()) {
int returnedtopElement = topElement;
topElement--;
System.out.println("Element Popped from Stack is :" + arr[returnedtopElement]);
return arr[returnedtopElement];
} else {
System.out.println("Stack is empty...");
return -1;
}
}
// this method returns topmost element from stack
public int peek() {
if(!this.isEmpty())
return arr[topElement];
else
{
System.out.println("Stack is Empty");
return -1;
}
}
// this method checks stack is empty
public boolean isEmpty() {
return (topElement == -1);
}
public boolean isStackFull() {
return (size - 1 == topElement);
}
public static void main(String[] args) {
StackArrayImpl impl = new StackArrayImpl(10);
impl.pop();
System.out.println("--------------");
impl.push(210);
impl.push(310);
impl.push(50);
impl.push(400);
impl.push(410);
impl.push(610);
impl.push(70);
impl.push(4);
impl.push(1);
impl.push(20);
impl.push(21);
System.out.println("------------------");
impl.pop();
impl.pop();
impl.pop();
System.out.println("------------------------");
}
}Output:
In this example, we have defined the initial capacity of the stack using the constructor. Also, we have created different methods corresponding to various operations available in the stack. The above code demonstrates the implementation of push, pop, peek, isEmpty, and isStackFull operations on an array-based stack.
Conclusion
The above article explains implementing a stack using an array as the underlying data structure. We develop a clear understanding of how the stack facilitates different operations.
Recommended Articles
This is a guide to Array Implementation of Stack. Here we discuss the Introduction and importance of using array implementation of a stack. You may also look at the following articles to learn more –
