in which they were added. The add element and remove element operations are conventionally called push and pop, respectively.
One of the ways to implement a stack is by using a dynamic array, an array that changes size as needed
when elements are added. The main advantage of dynamic arrays over linked lists is that arrays offer random access to the array elements (you can immediately access any element in the array if you know its index). However, operations on a stack always work on one end of the data structure (the top of the stack), so the random accessibility of a dynamic array gains you little. In addition, as a dynamic array grows, it must occasionally be resized, which can be a time-consuming operation as elements are copied from the old array to the new array.
Linked lists usually allocate memory dynamically for each element. Depending on the overhead of the memory allocator, these allocations are often more time consuming than the copies required by a dynamic array, so a stack based on a dynamic array is usually faster than one based on a linked list.
Basic Stack Operations
The Stack element is represented in StackNode private class and Stack functionalities are represented in Stack class. This class is generic.
// last-in-first-out (LIFO) data structure
public class Stack<T> {
private class StackNode {
private T data;
private StackNode next;
public StackNode() {
this.data = null;
this.next = null;
}
public StackNode(T data) {
this.data = data;
this.next = null;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public StackNode getNext() {
return next;
}
public void setNext(StackNode next) {
this.next = next;
}
}
private StackNode lastNode;
private int size;
// Empty list constructor
public Stack() {
this.lastNode = new StackNode();
size = 0;
}
// Construct a stack with a single node
public Stack(T data) {
this();
this.push(data);
}
}
Push
inserting an item into a stack
// Push a node to the stack
public void push(T data) {
StackNode node = new StackNode(data);
// if the stack is empty
if (this.lastNode.getData() == null) {
this.lastNode = node;
} else {
StackNode lastNode = this.lastNode;
node.setNext(lastNode);
this.lastNode = node;
}
this.size++;
}
Pop
deleting an item from the stack
// Pull the last element
public T pop() {
if (size > 0) {
StackNode node = this.lastNode;
StackNode previousNode = node.getNext();
if (previousNode != null) {
this.lastNode = previousNode;
}
size--;
return node.getData();
}
return null;
}
Size
// Return size of the stack
public int getSize() {
return this.size;
}
Source Code
// last-in-first-out (LIFO) data structure
public class Stack<T> {
private class StackNode {
private T data;
private StackNode next;
public StackNode() {
this.data = null;
this.next = null;
}
public StackNode(T data) {
this.data = data;
this.next = null;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public StackNode getNext() {
return next;
}
public void setNext(StackNode next) {
this.next = next;
}
}
private StackNode lastNode;
private int size;
// Empty list constructor
public Stack() {
this.lastNode = new StackNode();
size = 0;
}
// Construct a stack with a single node
public Stack(T data) {
this();
this.push(data);
}
// Push a node to the stack
public void push(T data) {
StackNode node = new StackNode(data);
// if the stack is empty
if (this.lastNode.getData() == null) {
this.lastNode = node;
} else {
StackNode lastNode = this.lastNode;
node.setNext(lastNode);
this.lastNode = node;
}
this.size++;
}
// Pull the last element
public T pop() {
if (size > 0) {
StackNode node = this.lastNode;
StackNode previousNode = node.getNext();
if (previousNode != null) {
this.lastNode = previousNode;
}
size--;
return node.getData();
}
return null;
}
// Return size of the stack
public int getSize() {
return this.size;
}
// Return a string representation of the list
public String toString() {
StackNode currentNode = this.lastNode;
StringBuffer buffer = new StringBuffer();
buffer.append("{");
for (int i = 0; currentNode != null; i++) {
if (i > 0) {
buffer.append(",");
}
T dataT = currentNode.getData();
buffer.append(dataT == null ? "" : dataT);
currentNode = currentNode.getNext();
}
buffer.append("}");
return buffer.toString();
}
}
JUnit Test
import static org.junit.Assert.assertTrue;
import org.junit.Test;
public class StackTest {
@Test
public void testStack() {
Stack<Integer> stack = new Stack<Integer>();
assertTrue(0 == stack.getSize());
}
@Test
public void testStackObject() {
Stack<Integer> stack = new Stack<Integer>(17);
assertTrue(1 == stack.getSize());
}
@Test
public void testPush() {
Stack<Integer> stack = new Stack<Integer>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
assertTrue(5 == stack.getSize());
}
@Test
public void testPop() {
Stack<Integer> stack = new Stack<Integer>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
assertTrue(5 == (Integer) stack.pop());
}
@Test
public void testGetSize() {
Stack<Integer> stack = new Stack<Integer>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
assertTrue(5 == stack.getSize());
}
}
No comments:
Post a Comment