Stacks and Queues

Stack

LIFO = "last in first out"
Examine the item most recently added.
push()
pop()

implementation -How it works in linked-list

inner class
private class Node
{
 String item;
 Node next;
}

/* === pop() === */
String item = first.item;
first = first.next;   //delete first node
return item;

/* === push() === */
Node oldfirst = first;
first = new Node();
first.item = "not";
first.next = oldfirst;

Queue

FIFO = "first in first out"
Examine the item least recently added.
enqueue()
dequeue()

implementation -How it works in linked-list

inner class
private class Node
{
 String item;
 Node next;
}

/* === dequeue() === */
String item = first.item;
first = first.next;   //delete first node
return item;

/* === enqueue() === */
Node oldlast = last;
//create a new node for the end
last = new Node();
last.item = "not";
//link the new node to the end of the list
oldlast.next = last;