算法:背包,栈,队列的简单实现,链式结构
博客专区 > gaomq 的博客 > 博客详情
算法:背包,栈,队列的简单实现,链式结构
gaomq 发表于5个月前
算法:背包,栈,队列的简单实现,链式结构
  • 发表于 5个月前
  • 阅读 2
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 十分钟定制你的第一个小程序>>>   

/**
 * Created by GAOMINGQIAN on 2017/6/4.
 * 背包的实现
 */
public class Bag<Item> implements Iterable<Item>{
    //链表的头结点
    private Node first;
    public class Node{
        Item item;
        Node next;
    }
    public void add(Item item){
        Node oldFirst=first;
        first=new Node();
        first.item=item;
        first.next=oldFirst;
    }
    @Override
    public Iterator<Item> iterator() {
        return new LinkedIterator();
    }
    public class LinkedIterator implements Iterator<Item>{
        private  Node currentNode=first;
        @Override
        public boolean hasNext() {
            return currentNode!=null;
        }
        @Override
        public Item next() {
            Item item=currentNode.item;
            currentNode=currentNode.next;
            return item;
        }
    }
}

大家注意一下上面背包实现的时候,链表指向的顺序。方向是从右向左,所以遍历输出时和add()的顺序相反。

/**
 * Created by GAOMINGQIAN on 2017/6/4.
 * 栈的实现
 */
public class Stack<Item> {
    //元素的数量
    private int N=0;
    //栈顶
    private Node first = null;
    public class Node {
        //存放的元素
        private Item item;
        private Node next;
    }
    //放元素
    public void push(Item item) {
        Node oldFirst = first;
        first = new Node();
        first.item = item;
        first.next = oldFirst;
        N++;
    }
    public Item pop() {
        if(isEmpty()){
            throw  new NullPointerException("已经没有元素");
        }
        Item item = first.item;
        first = first.next;
        N--;
        return item;
    }
    public boolean isEmpty(){
        return N==0;
    }
    public int size(){
        return N;
    }
}

栈的链表指向顺序是从左向右,在左端进行操作出入栈。

/**
 * Created by GAOMINGQIAN on 2017/6/4.
 * 队列的实现
 */
public class Queue<Item> {
    //存放的元素个数
    private int N = 0;
    //头
    private Node first;
    //尾
    private Node last;

    public class Node {
        Item item;
        Node next;
    }
    public void enqueue(Item item) {
        Node oldLast = last;
        last = new Node();
        last.item = item;
        if (isEmpty())
            first = last;
        else
           oldLast.next=last;
        N++;
    }
    public Item dequeue() {
        Item item = first.item;
        first=first.next;
        if (isEmpty()){
            last=null;
        }
        N--;
        return item;
    }
    public boolean isEmpty() {
        return N == 0;
    }
    public int size(){
        return N;
    }
}

队列的链表指向顺序是从左向右,右端出队,左端入队。

标签: 数据结构
共有 人打赏支持
粉丝 0
博文 30
码字总数 12659
×
gaomq
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: