Introduction to Array Implementation of Stack
Array implementation of stack can be defined as a mechanism through which all the operations supported by stack are implemented using an array as the basic data structure. As we are aware that stack is a linear data structure that is based on the Last-in-first-out strategy (LIFO). In this article, we will see how the stack is implemented using an array in java. We will see the importance and different uses of implementing stack using an array. Also, we will cover the complete java code example to demonstrate how an array is used to implement a stack with all the operations on stack taking place using an array.
Some of the major operations supported by stack are:
- Push: This operation adds an item to the stack, it will throw an exception in case the capacity of the stack is full.
- Pop: This removes the last inserted element from a stack that is elements are removed in reverse order of their insertion, it will throw an underflow exception in case 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 returns false.
- IsStackFull: Checks if a stack is full or not. Returns true if the given stack is full otherwise 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 to reverse a word can be solved using stack.
- Java Virtual machine use stack to store method calls and implement recursion.
- Syntax checking by the compiler is achieved using stack.
- A stack can be used in backtracking algorithms.
Due to the above applications stack is one of the most commonly used data structures in computer science.
Importance of Using Array Implementation of Stack
The foremost advantage of using an array for implementing stack is that it is more time-efficient than linked list implementation of the stack which takes extra time in allocating pointers of nodes whenever there is a change in the size of the stack. All the operations in case of an array-based implementation of a stack will be carried out in O (1) time.
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("------------------------");
}
}
4.8 (8,051 ratings)
View Course
Output:
In this example, we have defined the initial capacity of stack using constructor. Also, we have created different methods corresponding to different operations available in the stack. In the above code, we have seen how push, pop, peek isEmpty and isStackFull operations are carried out on an array similar to stack.
Conclusion
From the above article, we have a clear understanding of how a stack is implemented using an array is the data structure. Also, we have a clear idea of how different operations are carried out on stack.
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 –
