Array Implementation of Stack

Introduction to Array Implementation of Stack

Array implementation of the stack can be defined as a mechanism through which all the operations supported by the stack are implemented using an array as the basic data structure. We are aware that the stack is a linear data structure 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 a 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 the 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 if the stack’s capacity is full.
• Pop: This removes the last inserted element from a stack that is removed 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 to reverse a word can be solved using stack.
• Java Virtual machine uses a 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, the 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 a 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("------------------------");
}
}

Output:

In this example, we have defined the initial capacity of the stack using the 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 clearly understand how a stack is implemented using an array as the data structure. Also, we have a clear idea of how different operations are carried out on the 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 –

1. What is PHP Array?
2. Java List vs Array List
3. Stack vs Heap Memory
4. Stack vs Queue