Stack and Queue

Stacks

A stack is a data structure that uses a principle called Last-In-First-Out (LIFO), meaning that the last object added to the stack must be the first object removed from it.

At minimum, any stack, s, should be able to perform the following three operations:

• Peek: Return the object at the top of the stack (without removing it).
• Push: Add an object passed as an argument to the top of the stack.
• Pop: Remove the object at the top of the stack and return it.

The java.util package has a Stack class that implements these methods

 

Modifier and TypeMethod and Description

boolean	empty() Tests if this stack is empty.
E	peek() Looks at the object at the top of this stack without removing it from the stack.
E	pop() Removes the object at the top of this stack and returns that object as the value of this function.
E	push(E item) Pushes an item onto the top of this stack.
int	search(Object o) Returns the 1-based position where an object is on this stack.

Queues

A queue is a data structure that uses a principle called First-In-First-Out (FIFO), meaning that the first object added to the queue must be the first object removed from it. 

At minimum, any queue, q, should be able to perform the following two operations:

• Enqueue: Add an object to the back of the line.
• Dequeue: Remove the object at the head of the line and return it; the element that was previously second in line is now at the head of the line.

The java.util package has a Queue interface that can be implemented by a number of classes, includingLinkedList. Much like abstract classes, interfaces cannot be instantiated so we must declare a variable of type Queue and initialize it to reference a new LinkedList object.

 

Modifier and TypeMethod and Description

boolean	add(E e) Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.
E	element() Retrieves, but does not remove, the head of this queue. This method differs from peek only in that it throws an exception if this queue is empty.
boolean	offer(E e) Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions. When using a capacity-restricted queue, this method is generally preferable to add(E), which can fail to insert an element only by throwing an exception.
E	peek() Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
E	poll() Retrieves and removes the head of this queue, or returns null if this queue is empty.
E	remove() Retrieves and removes the head of this queue. This method differs from poll only in that it throws an exception if this queue is empty.