文档章节

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

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

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

© 著作权归作者所有

共有 人打赏支持
gaomq
粉丝 2
博文 53
码字总数 22928
作品 0
沈阳
程序员
队列

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

SkyHive ⋅ 2017/10/14 ⋅ 0

数据结构-栈&队列&Deque实现比较

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

IAM四十二 ⋅ 2017/10/22 ⋅ 0

C 算法与数据结构 队列

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

起什么name呢 ⋅ 2016/03/28 ⋅ 0

第一章 基础

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

Jonson ⋅ 2016/04/21 ⋅ 0

数据结构课程主页-2016级

  新学期,再度起程!   翻转的数据结构课程再度迎来新的一批同学。   前两年,资源建设基本完备,课堂方案逐渐完善,同学们对新型的学习方式设计给予了肯定(参见2014级问卷调查和201...

sxhelijian ⋅ 2017/08/30 ⋅ 0

技能篇-数据结构和算法篇-基础算法与结构( 一 )

一 : 科普一分钟 什么是数据结构和算法,二者有和联系呢. 其实一种是数据存储的方式,一种是一种实现功能的手段. 我最近经常做饭,打个比方,就好比做菜一样,我们所用的食材就是数据结构,我们做同...

TianTianBaby223 ⋅ 2017/08/06 ⋅ 0

stack顺序存储结构--array based stack

《偶刚开始学习数据结构,欢迎拍砖111》 栈是只能通过访问它的一段来实现数据存储的一种线性数据结构,换句话来说就是先进后出的原则,FILO,与队列刚好相反哈,现在只说stack。 栈包括以下几...

qmiwang ⋅ 2012/03/29 ⋅ 0

算法工程师成长计划

算法工程师成长计划 近年来,算法行业异常火爆,算法工程师年薪一般20万~100 万。越来越多的人学习算法,甚至很多非专业的人也参加培训或者自学,想转到算法行业。尽管如此,算法工程师仍然...

rainchxy ⋅ 2017/10/23 ⋅ 0

面试常考的常用数据结构与算法【简】

数据结构与算法,这个部分的内容其实是十分的庞大,要想都覆盖到不太容易。在校学习阶段我们可能需要对每种结构,每种算法都学习,但是找工作笔试或者面试的时候,要在很短的时间内考察一个人...

anlve ⋅ 05/01 ⋅ 0

C语言/C++编程新手入门基础知识整理学习

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界 ⋅ 04/01 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Java集合类总结笔记

一、集合类的层次关系 主要容器集合类的特点: ArrayList 一种可以动态增长和缩减的索引序列 LinkedList 一种可以在任何位置进行高效地插入和删除的有序序列 ArrayDeque 一种用循环数组实现的...

edwardGe ⋅ 8分钟前 ⋅ 0

spring RMI远程调用

RMI https://www.cnblogs.com/wdh1995/p/6792407.html

BobwithB ⋅ 13分钟前 ⋅ 0

Jenkins实践2 之基本配置

1 插件管理 系统管理->插件管理 在可选插件中可以自主安装插件 2 管理用户 系统管理->管理用户->新建用户 3 安全配置 系统管理->全局安全配置 授权策略 选择安全矩阵 然后添加现有的用户,赋...

晨猫 ⋅ 13分钟前 ⋅ 0

c++智能指针

1、是一种泛型类,针对指针类型的泛型类,会保存指针 2、重载了符号 *和-> 对智能指针使用这两个符号,相当于对保存的泛型使用这两个符号 3、当智能指针引用计数为0时,会去释放指针指向的资...

国仔饼 ⋅ 14分钟前 ⋅ 0

Spring Boot错误处理机制

1)、SpringBoot默认的错误处理机制 默认效果: 1)、浏览器,返回一个默认的错误页面 浏览器发送请求的请求头: 2)、如果是其他客户端,默认响应一个json数据 原理: 可以参照ErrorMvcAut...

小致dad ⋅ 16分钟前 ⋅ 0

ftp连接不上的终极办法 SFTP

假如FTP由于各种原因就是连不上,那么用SFTP协议吧,使用登录服务器的账号密码。

sskill ⋅ 20分钟前 ⋅ 0

Unity 围绕旋转角度限制(Transform.RotateAround)

在 Unity 中可以利用 Transform.RotateAround 围绕指定物体进行旋转,但某些情况下可能需要对旋转角度进行控制。我是先计算出预设角度大小,然后判断是否在限定角度范围内是则进行旋转。 相关...

大轩 ⋅ 21分钟前 ⋅ 0

阿里沙箱环境支付宝测试demo

阿里支付宝支付和微信支付,包括:阿里沙箱环境支付宝测试demo,支付宝支付整合到spring+springmvc+mybatis环境和微信整合到如上环境,功能非常齐全,只需要修改对应的配置文件即可,帮助文档...

码代码的小司机 ⋅ 24分钟前 ⋅ 0

JDK1.6和JDK1.7中,Collections.sort的区别,

背景 最近,项目正在集成测试阶段,项目在服务器上运行了一段时间,点击表格的列进行排序的时候,有的列排序正常,有的列在排序的时候,在后台会抛出如下异常,查询到不到数据,而且在另外一...

tsmyk0715 ⋅ 41分钟前 ⋅ 0

C++ 中命名空间的 5 个常见用法

相信小伙伴们对C++已经非常熟悉,但是对命名空间经常使用到的地方还不是很明白,这篇文章就针对命名空间这一块做了一个叙述。 命名空间在1995年被引入到 c++ 标准中,通常是这样定义的: 命名...

柳猫 ⋅ 45分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部