Stack Implementation Using Array
A stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle. A stack is a limited access data structure – elements can be added and removed from the stack only at the top.
push operation adds an item to the top of the stack.
pop removes the item from the top.
Additionally, a peek operation may give access to the top without modifying the stack.
A helpful analogy is to think of a stack of books. you can remove only the top book, also you can add a new book on the top.
Applications
The simplest application of a stack is to reverse a word. You push a given word to stack – letter by letter – and then pop letters from the stack.
Another application is an "undo" mechanism in text editors; this operation is accomplished by keeping all text changes in a stack.
Java Virtual Machine(JVM) uses stack in method calls and recursion.
compiler's syntax check for matching braces is implemented by using stack.
space for parameters and local variables is created internally using a stack.
space for parameters and local variables is created internally using a stack.
In backtracking algorithms can be implemented using stack.
Implementation
In the standard library of classes, the data type stack is an adapter class, meaning that a stack is built on top of other data structures. The underlying structure for a stack could be an array, a vector, an ArrayList, a linked list, or any other collection. Regardless of the type of the underlying data structure, a Stack must implement the same functionality. This is achieved by providing a unique interface:
interface StackInterface<AnyType>
{
public boolean isEmpty();
public AnyType pop() throws StackException;
public AnyType peek() throws StackException;
public void push(AnyType e) throws StackException;
public void clear();
}
Userdefined Stack Exception class
class StackException extends RuntimeException
{
public StackException(String name)
{
super(name);
}
public StackException()
{
super();
}
}Array Based Implementation
In an array-based implementation we maintain the following fields:
- an array A of a default size (>= 1),
- the variable top that refers to the top element in the stack and
- the capacity that refers to the array size.
The variable top changes from -1 to (capacity-1). We say that a stack is empty when top = -1, and the stack is full when top = (capacity-1).
In a fixed-size stack abstraction, the capacity stays unchanged, therefore when top reaches capacity, the stack object throws an exception.
public class ArrayStack<AnyType> implements StackInterface<AnyType>
{
private static final int DEFAULT_CAPACITY = 15;
private int top; // reference to the top element
private AnyType[] A;
/**
* Creates a Stack of the size initialCapacity
*/
public ArrayStack(int initialCapacity)
{
if (initialCapacity <= 0)
A = (AnyType[]) new Object[DEFAULT_CAPACITY];
else
A = (AnyType[]) new Object[initialCapacity];
top = -1; //stack is empty
}
/**
* Creates a Stack with the default capacity
*/
public ArrayStack()
{
this(DEFAULT_CAPACITY);
}
/**
* Tests if the stack is empty.
*/
public boolean isEmpty()
{
return top==-1;
}
/**
* Returns the top item without its removal.
*/
public AnyType peek()
{
if (isEmpty()) throw new StackException("Stack is empty");
return A[top];
}
/**
* Removes and returns the item at the top of this stack.
*/
public AnyType pop()
{
AnyType x = peek();
A[top] = null; //make sure the object is destroyed
top--;
return x;
}
/**
* Inserts an item onto the top of the stack.
*/
public void push(AnyType e)
{
if (top == A.length) throw new StackException("Stack has overflowed");
top++;
A[top] = e;
}
/**
* Removes all items from the Stack.
*/
public void clear()
{
for(int i = 0; i <= top; i++)
A[i] = null;
top = -1;
}
/**
* Returns a string representation of the Stack.
*/
public String toString()
{
if(isEmpty()) return "[ ]";
StringBuffer out = new StringBuffer("[");
for(int i = 0; i < top; i++)
out.append(A[i] + ", ");
out.append(A[top] + "]");
return out.toString();
}
public static void main(String[] args)
{
ArrayStack<Integer> s = new ArrayStack<Integer>(6);
try
{
for(int i = 0; i < 6; i++) s.push(i);
//s.clear();
System.out.println(s);
for(int i = 0; i < 5; i++) s.pop();
System.out.println(s);
}
catch (StackException e)
{
System.err.println(e);
}
}
}
That's all for this topic. If you guys have any suggestions or queries, feel free to drop a comment. We would be happy to add that in our post. You can also contribute your articles by creating contributor account here.
Happy Learning 🙂
If you like the content on CodePumpkin and if you wish to do something for the community and the planet Earth, you can donate to our campaign for planting more trees at CodePumpkin Cauvery Calling Campaign.
We may not get time to plant a tree, but we can definitely donate ₹42 per Tree.
About the Author
Tags: Array, DataStructure, Java, Stack
Comments and Queries
If you want someone to read your code, please put the code inside <pre><code> and </code></pre> tags. For example:<pre><code class="java"> String foo = "bar"; </code></pre>For more information on supported HTML tags in disqus comment, click here.
