算法系列笔记（二）利用链表实现栈和队列

引言

上一次我们实现了泛型栈，并在最后粗略带过栈的迭代器的功能的实现。然而我们注意到我们是用数列去存储数据，但我们实现不定容的栈其实是和数组定容的特性是不搭的，导致我们就被迫建立方法resize,并在resize中使用大规模的数组遍历复制。这明显是比较消耗性能的。所以我们今天采用另外一种方式代替数组来存储数据，这就是链表

链表的介绍

链表你可以想象作一根线上有一颗颗珠子，老实说不是一根线是一段段线，连接相邻的两颗珠子。这样就能将一个个离散的珠子（离散的数据）联系在一起。是的，珠子应该是存储数据的实体，但珠子应该知道它相邻的珠子是谁，否则线没法将他们联系起来，所以就还必须存储这个相邻珠子的具体身份或地址（由于我这里是构建单向链表，所以珠子只需要知道它前一个珠子就行（当然你也可以构建双向的））

由于我觉得珠子其实就是一个个离散的点，所以我们这里将珠子叫作point

综上，可以归结出链表的实现必须依靠一个个point，而point的实现有两点要求

1.存储数据
2.存储上一个point的身份标识（地址）

具体实现

public class Listforstack<T> {
    private point first;
    private int n;
    private class point{
        T data;
        point last;            //存储上一个point的地址
    }
    public boolean isempty(){
        return n==0;
    }
    public int size(){
        return n;
    }
    public void push(T d){
        point oldpoint=first;
        first=new point();
        first.data=d;
        first.last=oldpoint;
        n++;
    }
    public T pop(){
       T d=first.data;
       first=first.last;
       n--;
       return d;
    }
}

这里point中的point last本来我是想着弄指针的，后来想起这是java不是c++，本身就是指针操作。
其实倘若想实现双向列表的话，只需要在point的定义中添加一个point next存下一个point的地址就行

队列和背包

下面实现队列，简单介绍一下

栈我们知道是数据先进后出
队列和栈差不多不过是先进先出，就好像排队一样，先排的肯定是最先受到服务之类的

下面是利用单向链表的队列的实现

    public class Listforqueue<T> {
        private point last;
        private point first;
        private int n;
        private class point{
            T data;
            point next;             //存储下一个point的地址
            public point(T d) {
                data=d;
            }
        }
        public boolean isempty(){
            return n==0;
        }
        public int size(){
            return n;
        }
        public void add(T d){
            if(n==0){                         //对n=0时特判
                last=new point(d);
                last.next=null;
                first=last;
                n++;
            }
            else{
            point oldlast=last;
            last=new point(d);
            oldlast.next=last;
            last.next=null;
            n++;
            }
        }
        public T pop(){             //这是清除并返回第一个元素
            if(isempty()){
                return null ;
            }
            T d=first.data;
            first=first.next;           //不怕越界出错，最多是变成null而已
            n--;
            return d;
        }
    }

注意这个pop是弹出第一个元素

对了别忘了我们之前的迭代器的实现，其实和我们之前的数组实现栈的方式差不多，下面我就写一个队列的迭代器版本吧

import java.util.Iterator;

public class ListforqueueIter<T> implements Iterable<T>{
    private point last;
    private point first;
    private int n;
    private class point{
        T data;
        point next;             //存储下一个point的地址
        public point(T d) {
            data=d;
        }
    }
    public boolean isempty(){
        return n==0;
    }
    public int size(){
        return n;
    }
    public void add(T d){
        if(n==0){                         //对n=0时特判
            last=new point(d);
            last.next=null;
            first=last;
            n++;
        }
        else{
        point oldlast=last;
        last=new point(d);
        oldlast.next=last;
        last.next=null;
        n++;
        }
    }
    public T pop(){             //这是清除并返回第一个元素
        if(isempty()){
            return null ;
        }
        T d=first.data;
        first=first.next;           //不怕越界出错，最多是变成null而已
        n--;
        return d;
    }
    
    //直到为止现在和上面的实现没有任何区别
    
    public Iterator<T> iterator() {
        return new Iter();
    }
    private class Iter implements Iterator<T>{
        private point cur=first;      //cur表示迭代器当前位置
        public boolean hasNext(){
            return cur.next!=null;
        }
        public void remove(){           //这个是删除当前位置的下一个元素
            point newnext=cur.next.next;   
            cur.next.next=null;
            cur.next=newnext;
        }
        public T next(){                //返回当前迭代器元素，迭代器往下移动*1
            T d =cur.data;
            cur=cur.next;
            return d;
        }
    }
}

注意这里的remove是删除当前迭代器位置的下一个元素，要删除迭代器位置的元素需要依靠双向链表。