文档章节

算法:背包,栈,队列的简单实现,链式结构

gaomq
 gaomq
发布于 2017/06/04 15:48
字数 375
阅读 5
收藏 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;
    }
}

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

© 著作权归作者所有

共有 人打赏支持
gaomq
粉丝 3
博文 59
码字总数 23993
作品 0
合肥
程序员
私信 提问
数据结构-栈&队列&Deque实现比较

栈 栈: 限定仅在表尾进行插入和删除操作的线性表; 后进先出(LIFO)。 在表尾进行操作,表尾是栈顶;最新进栈的元素在栈底。 栈的ADT Stack_ADT 进栈&出栈 栈 栈的存储结构实现 顺序栈 栈也...

IAM四十二
2017/10/22
0
0
C 算法与数据结构 队列

队列 线性数据结构的一种。 特点 先进先出 入队的那一头叫队尾,出队的那一头叫队首。 队列里的指针域总是指向下一个节点。 下面是队列的链式存储结构C代码实现 #include <stdio.h>#include...

起什么name呢
2016/03/28
19
0
队列

队列 队列是一种可以实现先进先出(first in first out,FIFO)的存储结构。与栈不一样的是,队列规定只在一端进行插入操作,在另一端进行删除操作。允许插入的一端叫做队尾(rear),允许删除的一...

SkyHive
2017/10/14
0
0
第一章 基础

什么是算法 ? 算法是编写一段计算机程序一般是实现一种已有的方法来解决某个问题. 在计算机领域里,我们用算法这个词来描述一种有限定,确定,有效的并适用计算机程序来实现解决的方法. 例 : 求...

Jonson
2016/04/21
27
0
《大话数据结构》读书笔记(1)

其实去年的时候就看过这本书了。只是,基本上是走马观花, 了解了一些基本概念。这次,为了看懂里面的代码,又特地去复习了一下c语言。还记得上次看的时候,感觉算法果然名不虚传,真的难!现...

幽灵君
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

大数据学习之大数据技术笔记—spring入门

篇一 spring介绍 spring.io 官网 快速开始 Aop 面向切面编程,可以任何位置,并且可以细致到方法上 连接框架与框架 Spring 就是 IOC AOP 思想 有效的组织中间层对象一般都是切入 service 层 ...

董黎明
12分钟前
2
0
Linux如何查看进程、杀死进程、启动进程等常用命令

关键字: linux 查进程、杀进程、起进程 1.查进程 ps命令查找与进程相关的PID号: ps a 显示现行终端机下的所有程序,包括其他用户的程序。 ps -A 显示所有程序。 ps c 列出程序时,显示每个程...

临江仙卜算子
30分钟前
3
0
ASP.NET Core MVC 静态文件配置

在启动文件中添加以下配置 public class Startup{ public IServiceProvider ConfigureServices(IServiceCollection services) { services.AddDirectoryBrowser(); ......

whltian
41分钟前
1
0
linux之自定义命令

本人使用的是ubuntu系统,不喜欢建各种桌面快捷链接,但是每次启动个软件,去查找又麻烦,所以自定义了命令,来快捷的启动应用: 1、修改/etc/bash.bashrc,在文件末尾,加上如下List-1中的内...

克虏伯
48分钟前
7
0
linux基础

系统安全 sudo su chmod setfacl 进程管理 w top ps kill pkill pstree killall 用户管理 id usermod useradd groupad userdel 文件系统 mount umount fsck df du 网络应用 curl telnet mail......

关元
50分钟前
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部