## Stacks and Queues

Stacks and Queues are pretty similar data structures. The difference is in how they remove elements.

A Stack is LIFO – Last In First Out. Much like a stack of books.
A Queue is FIFI – First In First Out. If you are the first to line up, you are the first to come out.

While a Queue is more like when you are waiting at a super market. FILO – First in Last Out.

The are both linear data structures.
They can be implemented as Arrays or Linked Lists.

Here is a Stack and Queue implemented as a Linked List.

Stack.java

```public class Stack {

private class Node {
private int data;
private Node next;
private Node (int data) {
this.data = data;
}
}

private Node top; // add and remove things here

public boolean isEmpty() {
}

public int peek() {
}

public void push(int data) {
// Create new node
// Set it's next to be top
// Set top to be the new node

Node node = new Node(data);
node.next = top;
top = node;
}

public int pop() {
// Store the value you want to return
// Set the current top.next to be the new top
// return the value

// without null checks
int data = top.data;
top = top.next;
return data;

// with null check
//        int data = top.data;
//
//        if (top.next != null) {
//            top = top.next;
//        } else  {
//            top = null;
//        }
//        return data;
}
}
```

Queue.java

```public class Queue {

private class Node {
private int data;
private Node next;
private Node (int data) {
this.data = data;
}
}

private Node head; // remove things here
private Node tail; // add things here

public boolean isEmpty() {
return head == null;
}

public int peek() {
}

public void add(int data) {
// Create a new node
// Set the current tail.next to point to this new node
// Then set the new node to be the new tail

Node newTail = new Node(data);
if (tail != null) {
tail.next = newTail;
}
tail = newTail;

// handle case of first element where head is null
if (head == null) {
}
}

public int remove() {
// Point the head at the current head next
int data = head.data;