Uncategorized

Stack with O(1) push complexity

This is a stack program where the algorithm works on Last in First Out (LIFO) concept. This is a typical stack program with insertion complexity as O(1) i.e constant.


/**
*
*/
package java8pract.datastructures;

import java.util.ArrayList;
import java.util.List;

/**
* @author prabhukvn
*
*/
public class CustomStack<T extends Comparable> {
Node firstNode;
Node lastNode;
Node tempNode;
int stackSize = 0;

public void push(T element) {
Node node = null;
if (null == firstNode) {
node = new Node(null, element, null);
firstNode = node;
stackSize++;

} else {

Node middleNode = tempNode;
node = new Node(middleNode, element, null);
middleNode.next = node;
lastNode = node;
stackSize++;
}
tempNode = node;

}

public int getSize() {
return this.stackSize;
}

public T pop() {

T element = lastNode.element;
lastNode = lastNode.previous;
lastNode.next=null;
stackSize--;
return element;

}

/**
* Get all the elements in linked list
*
* @return
*/
public List<Node> getAll() {
List<Node> list = new ArrayList();
Node temp = firstNode;
while (temp != null) {
list.add(temp);
System.out.println(temp.element);
temp = temp.next;

}
return list;
}

}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s