Stack: Stack is the data structure which works on the concept of LIFO (Last In First Out). Consider one real time example of stack ... lets assume there is a box in which i keep books one over another. So if i want to take book out of the box then the book which enters last in the box gets out first from the box. Stack data structure can be implemented with two ideas one using Array and another using Link List. Now lets discuss concept of Stack implementation using Array. Here we are going to create an array which dynamically grows by twice its size.
Here we have got some frequently used methods. Now here we go ...
push(): Pushes data into the stack.
pop(): Removes data from the stack.
top(): Method delivers top element of the stack.
isEmpty(): This method returns true id stack is empty and false if not.
length(): This method returns integer value as the no of elements of the stack.
other method implementation is available in the Stack implementation in below class definition which violates the concept of stack. This method is sort().
Implementation:
We have got an Array with 5 as its size. We define a variable as top and this variable gets initialized by -1 and when we push element into the stack we place this value at the 0th location so before inserting element into the stack we increment the top variable by one the top becomes 0 and we place the value into stack and same process goes on till the stack is full.
Once stack is full we have to do a process to increase the size of stack and we can achieve by creating an array with double the size of the array and we copy stack elements into the newly created array so once again we have got enough space in new array. We can do the implementation by incrementing its size by fixed size such as 5 rather than doubling the size of the array. Doubling the size will take more space but incrementing the size of array by fixed number will take more time as we may need to copy it more frequently. Now which implementation you choose will be based on your requirement, if you have enough resources (memory) then we have to go with the bigger size array.
Challenges:
other method implementation is available in the Stack implementation in below class definition which violates the concept of stack. This method is sort().
Implementation:
We have got an Array with 5 as its size. We define a variable as top and this variable gets initialized by -1 and when we push element into the stack we place this value at the 0th location so before inserting element into the stack we increment the top variable by one the top becomes 0 and we place the value into stack and same process goes on till the stack is full.
Once stack is full we have to do a process to increase the size of stack and we can achieve by creating an array with double the size of the array and we copy stack elements into the newly created array so once again we have got enough space in new array. We can do the implementation by incrementing its size by fixed size such as 5 rather than doubling the size of the array. Doubling the size will take more space but incrementing the size of array by fixed number will take more time as we may need to copy it more frequently. Now which implementation you choose will be based on your requirement, if you have enough resources (memory) then we have to go with the bigger size array.
Challenges:
- We may have got Stack Full Exception, if we have not implemented dynamic incrementation. As we have got an Array which grows as per need, we will never face Stack Full Exception.
- We will get another type of Exception, i.e. Stack Empty Exception, if we get pop() method call again and again. Once the stack is empty i.e no more element to remove then we can display Stack Empty Exception.
/*
This class creates a dynamically growing stack. This class starts with array size 5 but once this stack array gets full this class grows by double its size. Growing a stack can be increased by desired no of size.
*/
package com.ds.stack;
public class StackArray
{
Integer[] stack;
public int top;
public StackArray()
{
stack = new Integer[5];
top = -1;
}
public void push(int value)
{
int arrLen = stack.length;
if (top == arrLen - 1) {
copyArray(arrLen);
}
stack[++top] = value;
}
public int pop()
{
if (top == -1) {
System.out.println("Stack is empty");
return -1;
}
int poppedElement = stack[top];
stack[top--] = null;
return poppedElement;
}
public Integer top()
{
int lastIndex = (stack.length) - 1;
Integer top = null;
for (int i = lastIndex; i >= 0; i--) {
Integer arrayVal = stack[i];
if (arrayVal != null) {
top = arrayVal;
break;
}
}
return top;
}
public boolean isEmpty()
{
int len = stack.length;
for (int i = 0; i < len; i++) {
if (stack[i] != null) {
return false;
}
}
return true;
}
public int length()
{
return top + 1;
}
public Integer[] sort(StackArray stack)
{
StackArray tmpStack = new StackArray();
while (!stack.isEmpty()) {
int tmp = stack.pop();
while (!tmpStack.isEmpty() && tmpStack.top() > tmp) {
int poppedElement = tmpStack.pop();
stack.push(poppedElement);
}
tmpStack.push(tmp);
}
stack.stack = tmpStack.stack;
return tmpStack.stack;
}
private void copyArray(int len)
{
Integer[] dummyStack = new Integer[len * 2];
for (int i = 0; i < len; i++) {
dummyStack[i] = stack[i];
}
stack = dummyStack;
}
private void printStack(Integer[] stackArray)
{
int arrLen = stackArray.length;
String printString = "";
for (int i = 0; i < arrLen; i++) {
Integer arrayVal = stackArray[i];
if (arrayVal == null) {
break;
}
printString += arrayVal.toString() + " --> ";
}
if ("".equals(printString)) {
System.out.println("Stack is empty");
} else {
System.out.println(printString);
}
}
public static void main(String[] args) throws Exception
{
StackArray stack = new StackArray();
stack.push(4);
stack.push(3);
stack.push(5);
stack.push(7);
stack.push(2);
stack.push(1);
stack.printStack(stack.stack);
//stack.sort(stack);
stack.pop();
stack.pop();
stack.pop();
stack.printStack(stack.stack);
System.out.println("Length of the stack is " + stack.length() + " top element is " + stack.top() + " top index "+stack.top);
}
}
Comparison: We got to compare both the implementation i.e. Array implementation and Link List implementation. Lets discuss both the implementation then you will be in better position to decide which implementation is better.
Array: Array implementation takes constant time for push(), pop(), top(), length() as we have got top variable which gives us the exact location of the element for pop(), push() and other described methods. The only problem with this concept is when we have to use dynamic array we need n time to copy the elements in new array which has been created to eliminate Stack Full Exception.
If we have the scenario where the total no of element count is fixed then array implementation of stack is preferable over Link List implementation of Stack.
Link List: Link list implementation need n time for every push(), pop() and other operation as we need to iterate form the first node to the last node where element needs to be push(), pop() or other operations. So here we have got the idea of both the concepts and based on the scenario we need to use for better performance.
No comments:
Post a Comment