This is my first post on stack data structure. In this post I am sharing my code of a simple Stack of integers which is internally implemented using integer array.
Stack
A stack is a basic data structure that can be logically thought as
linear structure represented by a real physical stack or pile, a
structure where insertion and deletion of items takes place at one end
called top of the stack. The basic concept can be illustrated by
thinking of your data set as a stack of plates or books where you can
only take the top item off the stack in order to remove things from it.
- Push and Pop
- peek
- is Full and is Empty
- My Stack Interface.
- Array Based Implementation.
Basic stack Operations:
Push and Pop
A stack has two fundamental operations - Push and Pop.
The
Push operation stores something on the top of the stack and the
Pop operation retrives something from the top of the stack.
Peek
Peek operation returns top element from the stack without removing it from the stack. Peek is not a fundamental stack operation but it is usually implemented in stack ADT.
Is Empty and Is Full
When stack is empty and pop operation is called then stack should throw "Stack underflow error" and if stack is already full and pop operation is called then we should throw "Stack overflow error".
So as to avoid these two errors we implement Is Empty and Is Full methods. Similar to peek, "Is Empty" and "Is Full" are also not fundamental stack operation.
My Stack Interface
I am creating Stack interface for my Stack ADT. Lets see the code:
public interface StackInterface {
//Method to push data onto stack
public boolean push(int data);
//Method to pop topmost element from stack or most recently added element in stack
public Integer pop();
// This is not a basic stack operation
// This method should allow a user to see the top most element in stack
// it is similar to popping and pushing element again.
public Integer peek();
//method should return true if stack is empty else false
public boolean isEmpty();
//Method should return true if stack is full else false
public boolean isFull();
}
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.
We say that a stack is
empty when
top = -1, and the stack is full when
top = capacity-1. The variable
top changes from -1 to
capacity - 1.
Below is my code for implementing integer stack using array:
public class StackUsingIntArray implements StackInterface {
// Every stack has a maximum capacity i.e. number of objects it can hold.
private static final int CAPACITY = 10;
//Top will always point to most recently added element in stack therefore
//top * -1 implies stack is empty
private int top = -1;
// array to hold stack elemnts.lt is initialized to capacity of stack
private int[] stackArray = new int[CAPACITY];
@Override
public boolean push(int data) {
//Check if stack is fullIf it is full then we show Stack overflow message
if (isFull()) {
System.out.println("Stack overflow");
return false;
} else {
stackArray[++top] = data;
return true;
}
}
@Override
public Integer pop() {
//Check if stack is empty If it is empty then we show Stack underflow message
if (isEmpty()) {
System.out.println("Stack underflow");
} else {
//decrementing top by one to make second element from top as top
top--;
//we will be returning top+1 value from array as we have already
//made top to point second element in stack
return (Integer) stackArray[top + 1];
}
return null;
}
@Override
public Integer peek() {
// we implement peek by first popping top element then pushing it back
Integer element = null;
if (!isEmpty()) {
element = pop();
push(element);
}
return element;
}
@Override
public boolean isEmpty() {
return top == -1;
}
@Override
public boolean isFull() {
return top == CAPACITY-1;
}
//This method just gives view of the stack. As there are only two operation
//for stack i.e. push and pop so in theory we can never print a stack
//without calling those two methods
public void printStack() {
System.out.print("[");
for (int i = top; i >= 0; i--) {
System.out.print(" " + stackArray[i]);
}
System.out.print(" ]");
}
public static void main(String[] args) {
StackUsingIntArray stack = new StackUsingIntArray();
stack.pop();
stack.push(40);
stack.pop();
stack.push(50);
stack.pop();
stack.push(50);
stack.push(11);
stack.pop();
stack.push(50);
stack.push(32);
stack.pop();
stack.pop();
stack.push(55);
stack.pop();
stack.push(68);
stack.pop();
stack.push(75);
stack.push(-12);
stack.printStack();
System.out.println();
System.out.println("=============================");
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
stack.printStack();
}
}
If we run the program we will get output like this:
Output
================================================================================
Stack underflow
[ -12 75 50 ]
====================
-12
75
50
Stack underflow
null
Stack underflow
null
Stack underflow
null
Stack underflow
null
[ 5 4 3 2 1 ]
Please share your
comments if you find anything incorrect, or you want to share more
information about the topic discussed above.
For further reading:
Stack implementation using link list
Stack implementation by link list node,
Stack implementation using doubly link list
Stack implementation by doubly link list node .
For complete listing see data structure and algorithm page
No comments :
Post a Comment