Every stack has a size that determines how many nodes it can accommodate. Attempting to push a node in a full stack will result in a stack overflow. The program may crash due to a stack overflow.
A stack is illustrated in the given image. stackA.push(xg)
will result in a stack overflow since the stack is already full.
A stack is a data structure that follows a last in, first out (LIFO) protocol. The latest node added to a stack is the node which is eligible to be removed first. If three nodes (a
, b
and, c
) are added to a stack in this exact same order, the node c
must be removed first. The only way to remove or return the value of the node a
is by removing the nodes c
and b
.
The stack data structure has three main methods: push()
, pop()
and peek()
.
The push()
method adds a node to the top of the stack.
The pop()
method removes a node from the top of the stack.
The peek()
method returns the value of the top node without removing it from the stack.
The .pop()
method of the Java Stack
class removes the node at the top of the stack. It does so using the LinkedList
method .removeHead()
. It then decreases the stack size
variable, returns the data of the removed node, and throws an error if the stack is empty. The helper method .isEmpty()
is used to verify this.
public String pop() {if (!this.isEmpty()) {String data = this.stack.removeHead();this.size--;return data;} else {throw new Error("Stack is empty!");}}
The main Java Stack
class constructor instantiates these variables:
stack
in the form of a LinkedList
maxSize
integer that determines the maximum number of nodes in the stacksize
integer that keeps track of the current size of the stackAnother Stack
constructor can be written that does not take any arguments. This constructor is used if no maxSize
value is specified as a parameter. It sets the maxSize
variable to Integer.MAX_VALUE
, which is the maximum integer in Java. This is stored in a variable DEFAULT_MAX_VALUE
. This effectively creates an unbounded stack.
public Stack() {this(DEFAULT_MAX_SIZE);}public Stack(int maxSize) {this.stack = new LinkedList();this.size = 0;this.maxSize = maxSize;}
A Java Stack
class can implement two helper methods to determine actions that should be taken with the stack:
.hasSpace()
returns a boolean
representing if there is space left in a bounded stack. It is used within the Stack
.push()
method..isEmpty()
returns a boolean
representing whether the stack is empty or not. It is used within the Stack
.pop()
and .peek()
methods.public boolean hasSpace() {return this.size < this.maxSize;}public boolean isEmpty() {return this.size == 0;}
The .peek()
method of the Java Stack
class examines, but does not remove, the top node of the stack. It returns the top node value if there is one, and returns null
if the stack is empty. The top node is accessed using the head
attribute of the linked list stack
. The top node’s data is accessed using the data
attribute of the head
node.
public String peek() {if (this.isEmpty()) {return null;} else {return this.stack.head.data;}}
A key method of the Java Stack
class is .push()
. This method takes a single String argument, data
, and adds this value to the top of the stack using the LinkedList
method .addToHead()
. It then increases the size
variable and throws an error if the stack is full to ensure that the stack does not overflow with nodes. It verifies this using the helper method .hasSpace()
.
public void push(String data) {if (this.hasSpace()) {this.stack.addToHead(data);this.size++;} else {throw new Error("Stack is full!");}}
A stack can be implemented in Java by creating a Stack
class with these methods. Each adjusts the stack in a different way.
LinkedList
for storage and a size
and maxSize
for tracking stack size.maxSize
property value of Integer.MAX_VALUE
by default..hasSpace()
determines if the stack has space for more data..isEmpty()
determines if the stack has any data..push()
adds new data to the top of the stack..pop()
removes the top element of the stack and return its value..peek()
looks at but does not remove the element at the top of the stack.public class Stack {public LinkedList stack;public int size;static final int DEFAULT_MAX_SIZE = Integer.MAX_VALUE;public int maxSize;public Stack() {this(DEFAULT_MAX_SIZE);}public Stack(int maxSize)public boolean hasSpace()public boolean isEmpty()public void push(String data)public String pop()public String peek()}