栈和队列——算法笔记

链表

链表可以方便地实现以下操作：

从表头添加元素

Node tmp = front;
front = new Node();
front.value = item;  // item为添加的元素
front.next = tmp;

考虑边界情况，当链表为空添加元素时的情况，需调整rear：

if(rear==null)
    rear = front;

从表尾添加元素

Node tmp = rear;
rear = new Node();
rear.value = item;  // item为添加的元素
tmp.next = rear;

考虑边界情况，当链表为空添加元素时的情况，需调整front，同时舍弃tmp.next = rear;

if(front==null)
    front = rear;

从表头删除元素

T tmp = front.value;
front = front.next;

考虑边界情况，当链表仅剩一个元素删除时，需调整rear：

if(front==null)
    rear = null;

栈

基于栈的特点，可以选择从表头添加元素，从表头删除元素，使用链表实现栈的代码如下：

public class Stack<T> {
    private class Node{
        T value;
        Node next;
    }
    private Node front;
    private int n;
    public void push(T item) {
        Node tmp = front;
        front = new Node();
        front.value = item;
        front.next = tmp;
        n++;
    }
    public T pop() {
        T tmp = front.value;
        front = front.next;
        n--;
        return tmp;
    }
    public int size() {
        return n;
    }
    public boolean isEmpty() {
        return front == null;
    }
}

队列

基于队列的特点，可以选择从表尾添加元素，从表头删除元素，使用链表实现队列的代码如下：

public class Queue<T>{
    private class Node{
        T value;
        Node next;
    }
    private Node front;
    private Node rear;
    private int n;
    public void enqueue(T item) {
        Node tmp = rear;
        rear = new Node();
        rear.value = item;
        if(tmp==null)
            front = rear;
        else
            tmp.next = rear;
        n++;
    }
    public T dequeue() {
        T tmp = front.value;
        front = front.next;
        if(front==null)
            rear = null;
        n--;
        return tmp;
    }
    public int size() {
        return n;
    }
    public boolean isEmpty() {
        return front == null;
    }
}