栈和队列——算法笔记

链表

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

从表头添加元素

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;
    }
}

算法

上一篇 【实验楼】HBASE教程——学习笔记
下一篇 Scala语言初步

添加新评论

*
*