文档章节

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

gaomq
 gaomq
发布于 2017/06/04 15:48
字数 375
阅读 4
收藏 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
博文 59
码字总数 23993
作品 0
合肥
程序员
队列

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

SkyHive
2017/10/14
0
0
C 算法与数据结构 队列

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

起什么name呢
2016/03/28
19
0
第一章 基础

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

Jonson
2016/04/21
27
0
数据结构-栈&队列&Deque实现比较

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

IAM四十二
2017/10/22
0
0
数据结构课程主页-2016级

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

sxhelijian
2017/08/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

python生成HTML报告

# -*- coding=utf-8 -*-# author=zyqimport timeclass Template(object): '''html报告''' HTML_TEMP=''' <!DOCTYPE html> <html lang="en"> <head......

小白兔_球球
28分钟前
1
0
模型融合资料汇总

https://blog.csdn.net/u012526003/article/details/79109418https://blog.csdn.net/willduan1/article/details/73618677https://blog.csdn.net/wstcjf/article/details/77989963?utm_so......

KYO4321
30分钟前
1
0
热更步骤

根据官方文档: http://docs.cocos.com/creator/manual/zh/advanced-topics/hot-update.html version_generator.js文件放到项目根目录下 注意步骤的顺序: 1.构建 2.根据构建目录运行下面命令...

Valiancer
31分钟前
2
0
小程序重写CheckBox样式

CheckBox /* 重写 checkbox 样式 *//* 未选中的 背景样式 */checkbox .wx-checkbox-input{ border-radius: 50%; width: 40rpx; height: 40rpx;}/* 选中后的 背景样式...

originDu
35分钟前
1
0
mysql自动安装脚本

[root@localhost_04 ~]# cat mysql.sh #!/bin/bash# "################检查本机安装mysql的基本条件########################"echo "Checking  user :"d=`id -u`if [ $d ......

芬野de博客
49分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部