- 浏览: 530711 次
- 性别:
- 来自: 杭州
文章分类
最新评论
-
GGGGeek:
看完了博主的博文,如果没猜错的话应该是浙大吧?很多优秀的人因为 ...
转《D君的故事》 以时刻警示自己 -
游牧民族:
楼主写的不错,学习了,最近对爬虫比较感兴趣,也写了些爬虫相关的 ...
通用爬虫框架及heritrix爬虫介绍 -
jimmee:
jerome_s 写道ice 你怎么看? 粗略的看了一下ice ...
MessagePack, Protocol Buffers和Thrift序列化框架原理和比较说明 -
jerome_s:
ice 你怎么看?
MessagePack, Protocol Buffers和Thrift序列化框架原理和比较说明 -
jimmee:
nk_tocean 写道照着做了,但是不行啊,还是乱码.先确认 ...
hive编写udf处理非utf-8数据
2.栈和队列
所谓的栈,是一个含有至少两个基本操作的抽象数据类型:插入新的元素;删除最近时间插入的元素。遵循FILO(First in,last out,先进后出)的原则。
所谓的队列,也是一个含有至少两个基本操作的抽象数据类型:插入新的元素;删除最久时间插入的元素。遵循FIFO(First in,first out,先进先出)的原则。
关于栈和队列的具体实现,我们即可以借助于数组,也可以采用链表来实现。
1) 栈的数组实现方式
2) 栈的链式实现方式
3) 队列的数组实现
数组的另一种更简单的实现方式:
4) 队列的链式实现方式
所谓的栈,是一个含有至少两个基本操作的抽象数据类型:插入新的元素;删除最近时间插入的元素。遵循FILO(First in,last out,先进后出)的原则。
所谓的队列,也是一个含有至少两个基本操作的抽象数据类型:插入新的元素;删除最久时间插入的元素。遵循FIFO(First in,first out,先进先出)的原则。
关于栈和队列的具体实现,我们即可以借助于数组,也可以采用链表来实现。
1) 栈的数组实现方式
public class MyStack<E> { public int count; public Object [] items; public boolean isEmpty(){ return count==0; } public MyStack (){ items=new Object[20]; count=0; } public MyStack (int len){ items=new Object[len]; count=0; } /** 重新调整数组的大小 **/ private void resize(int size){ Object [] newItems=new Object[size]; for(int i=0;i<count;i++){ newItems[i]=items[i]; } items=newItems; } public void push(E e){ if(count==items.length) resize(2*items.length); items[count++]=e; } public E pop(){ if(count==0) return null; E item=(E)items[count-1]; items[count-1]=null; count--; if(count>0&&count<=items.length/4) resize(items.length/2); return item; } public E peek(){ if(count==0) return null; E item=(E)items[count-1]; return item; } }
2) 栈的链式实现方式
public class MyStack<E> { private class Node{ E item; Node next; } Node head; public boolean isEmpty(){ return head==null; } public void push(E t){ Node node=new Node(); node.item=t; node.next=head; head=node; } public E pop(){ if(head==null) return null; E t=head.item; head=head.next; return t; } public E peek(){ if(head==null) return null; else return head.item; } }
3) 队列的数组实现
public class ArrayQueue<E> { private int front; private int rear; private int count; private int capacity; private int capacityIncrement; private Object[] itemArray; public ArrayQueue(){ front=0; rear=0; count=0; capacity=10; capacityIncrement=5; itemArray=new Object[capacity]; } public boolean empty(){ return count==0; } public void insert(E e){ if(count==capacity){ capacity+=capacityIncrement; Object [] newArray=new Object[capacity]; // for(int i=0;i<count;i++){ // newArray[i]=itemArray[i]; // } if(front<rear){ //如果元素位于itemArray[front:rear-1]中 for(int i=front;i<rear;i++){ newArray[i]=itemArray[i]; } }else{ //否则,将元素分成两个区间 //区间1:itemArray[0:rear-1] for(int i=0;i<rear;i++){ newArray[i]=itemArray[i]; } //区间2:itemArray[front:count-1] for(int i=front;i<count;i++){ newArray[i]=itemArray[i]; } front+=capacityIncrement;//然后,将front改为指向其新位置 } itemArray=newArray; } itemArray[rear]=e; rear=(rear+1)%capacity; count++; } public E remove(){ if(count==0){ return null; } else{ E temp=(E) itemArray[front]; itemArray[front]=null; front=(front+1)%capacity; count--; return temp; } } }
数组的另一种更简单的实现方式:
import java.util.NoSuchElementException; public class ArrayQueue { protected Object [] data; protected int size, head, tail; public ArrayQueue(){ final int INITIAL_LENGTH=100; data=new Object[INITIAL_LENGTH]; size=0; head=0; tail=-1; } public int size(){ return size; } public boolean isEmpty(){ return size==0; } public Object front(){ if(size==0) throw new NoSuchElementException(); return data[head]; } public void enqueue(Object element){ if(size==data.length){ //double the length of data Object [] oldData=data; data=new Object[data.length*2]; //copy oldData[head...OldData.length-1] //to data[0... OldData.length-1-head] System.arraycopy(oldData, head,data , 0, oldData.length-head); if(head>0) //copy oldData[0...tail] to data [head+1 .. oldlenght-1] System.arraycopy(oldData, 0, data, head+1, tail+1); head=0; tail=oldData.length-1; } tail=(tail+1)%data.length; size++; data[tail]=element; } public Object dequeue(){ if(size--==0){ throw new NoSuchElementException(); } Object element=data[head]; head=(head+1)%data.length; return element; } }
4) 队列的链式实现方式
public class ListQueue<E> { private class Node<E>{ E item; Node<E> link; } private Node<E> front,rear; private int count; public boolean empty(){ return count==0; } public void insert(E e){ //如果队列为空 Node<E> newNode=new Node<E>(); newNode.item=e; if(rear==null){ front=rear=newNode; }else{ rear.link=newNode; rear=newNode; } count++; } public E remove(){ if(count==0){ return null; }else{ E e=front.item; front=front.link; if(front==null){ rear=null; } count--; return e; } } public ListQueue<E> clone(){ ListQueue<E> Q=new ListQueue<E>(); for(Node<E> t=front;t!=null;t=t.link) Q.insert(t.item); return Q; } }
发表评论
-
moses安装记录
2016-12-11 11:00 01. moses的安装说明地址(注意,一定要安装好相应的bo ... -
翻译算法
2016-12-09 07:50 0翻译的概率T=argsMaxP(T|S)=P(T)P(S|T ... -
JPEG 简易文档 V2.15【转载】
2016-04-10 16:35 584JPEG 简易文档 V2.15 ------------- ... -
Java 并发之 ConcurrentSkipListMap 简述
2015-09-20 20:24 1082JCIP 提到了在 Java 6 中引入了两个新的并发集合类 ... -
最简单的平衡树(红-黑树)的实现
2015-09-04 08:04 1127在二叉搜索树(BST)的基础上,要实现一颗平衡树,可以使用 ... -
lucene索引创建的理解思路
2014-06-29 23:12 1429虽然lucene4很早就出来,但是这里仍然以lucene3. ... -
lucene的拼写检查的实现原理
2014-06-08 18:19 12751. 建索引时, 使用ngram的方式创建索引 Sp ... -
字符串相似算法-(3) NGram Distance
2014-06-08 17:54 4850就是N-Gram version of edit dista ... -
字符串相似算法-(2) Levenshtein distance
2014-06-08 16:32 2163编辑距离概念描述: ... -
字符串相似算法-(1) Jaro-Winkler Distance
2014-06-08 12:05 6448Jaro-Winkler Distance 算法 ... -
Lucene的数字范围搜索 (Numeric Range Query)原理
2014-04-05 16:08 134920. 全文索引的核心就是倒排索引. 1. 若 ... -
UDT协议-基于UDP的可靠数据传输协议的实现分析(7)-流量和拥塞控制
2014-04-02 20:53 4098流量控制 对于一个带宽1Gbps, RTT为100ms的网络 ... -
UDT协议-基于UDP的可靠数据传输协议的实现分析(6)-链接的建立和关闭
2014-04-01 22:47 19611. 模式有client/server mode(客户端, ... -
协议-基于UDP的可靠数据传输协议的实现分析(5)-可靠性怎么保证
2014-03-31 23:08 3738发送方的处理:1) 包发送确认后,由于还没有收到确认,先缓存 ... -
UDT协议-基于UDP的可靠数据传输协议的实现分析(4)-发送和接收的算法
2014-03-30 10:09 70580. 计时器udt有四种计时器: ACK, NAK, E ... -
UDT协议-基于UDP的可靠数据传输协议的实现分析(3)-包结构说明
2014-03-29 17:24 3135udt的包结构1. 数据包,基本结构如下: 0 ... -
UDT协议-基于UDP的可靠数据传输协议的实现分析(2)-为什么要用udt
2014-03-28 08:00 37170. AIMD算法的简单回顾 (1) 慢开始 ... -
UDT协议-基于UDP的可靠数据传输协议的实现分析(1)-准备工作
2014-03-27 12:52 37601. 协议实现方案: Yunhong Gu提出的rfc的草 ... -
mapreduce的一些算法设计,优化等(2)
2014-01-28 15:50 14171. 反序(order inversion ... -
mapreduce的一些算法设计,优化等(1)
2014-01-27 17:15 2026本系列是根据书籍《Da ...
相关推荐
作者采用了独特的方法将数据结构分成说明和实现两部分,并充分利用了已有的数据结构库(Java集合类API)。本书分为四个部分:第一部分讨论适合大多数应用的集合类API的一个子集,并覆盖基本的算法分析技术、递归和...
第一部分:数据结构与算法的基本概念 考核内容: 算法、算法正确性、复杂性; 算法的时间与空间复杂性级别; 数据类型、数据结构和表示、实现; 抽象数据类型的说明、高级语言对抽象数据类型的支持 考核要求: 理解...
基于C语言实现的基本数据结构定义以及简单的解题应用项目源码.zip基于C语言实现的基本数据结构定义以及简单的解题应用项目源码.zip基于C语言实现的基本数据结构定义以及简单的解题应用项目源码.zip基于C语言实现的...
作者采用了独特的方法将数据结构分成说明和实现两部分,并充分利用了已有的数据结构库(Java集合类API)。本书分为四个部分:第一部分讨论适合大多数应用的集合类API的一个子集,并覆盖基本的算法分析技术、递归和...
串基本操作演示代码加报告,报告里面有使用说明书
数据结构与算法分析,主要包括最基本的说明和基本算法举例说明.
全书内容浅显易懂,利用大量且丰富的图示与范例, 详解复杂的抽象理论,从最基本的数据结构概念开始 说明,再以Java工具加以诠释阵列结构、堆栈、链表 、队列、排序、查找等重要的概念,引领读者抓住重 点轻松进入...
JAVA实现链表 有序二叉树 队列的代码例子
数据结构课程设计,本课程设计是为了配合《数据结构》课程的开设,通过设计一完整的程序,使学生能达到如下要求: 1. 了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力; 2. 初步掌握软件开发过程...
包括习题与答案及要点,很实用啊 ... 数据结构的定义虽然没有标准,但是它包括以下三方面内容:逻辑结构、存储结构、和对数据的操作。这一段比较重要,我用自己的语言来说明一下,大家看看是不是这样。
数据结构形成了程序员基本数据结构工具箱(toolkit)。对于许多常见的问题,工 具箱里的数据结构是理想的选择。就像.NET Framework 中Windows应用程序开 发中的工具箱,程序员可以直接拿来或经过少许的修改就可以使用...
它基本上涉及了数据结构基础的“方方面面”。很难想象这书的厚度,居然能讲这么多内容(你看看算法导论有多厚就知道我在说什么了)。 它在内容上并不乏深度。高级数据结构部分并不容易,如果你第一次就全部耐心看完...
数据结构与算法分析 经典笔记学习笔记 1 前言 1.1 所选教材 1.2 写作原因 1.3 一些约定 1.4 历史记录 1.5 联系方式 2 单链表 2.1 代码实现 2.2 效率问题 2.3 应用:一元多项式(加法和乘法) 2.3.1 基础知识 2.3.2 ...
(3) 录入:可以录入航班情况(数据可以存储在一个数据文件中,数据结构、具体数据自定) (4) 查询:可以查询某个航线的情况(如,输入航班号,查询起降时间,起飞抵达城市,航班票价,票价折扣,确定航班是否满...
任 务 书 "题目:学生成绩管理系统 " "设计容与要求... 1968年美国唐·欧·克努特教授开创了数据结构的最初体系,他所著的《计算机程序设计技 巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构与其
一、基本概念和术语 数据(Data) 数据是信息的载体。它能够被计算机识别、存储和加工处理,是计算机程序加工...为了增加对数据结构的感性认识,下面举例来说明有关数据结构的概念。 【例1.1】 学生成绩表,见下表。
数据结构 一、基本信息数据结构 1、商品基本资料数据结构 说明: "Products "商品信息表 " "Barcode "一品多码表 " "Unit "商品单位表 " "Price "价格表 " "MedType "剂型表 " 2、往来单位基本信息 说明: "Clients ...
2.4.3 三种基本结构和改进的流程图 28 2.4.4 用N-S 流程图表示算法 29 2.4.5 用伪代码表示算法 30 2.4.6 用计算机语言表示算法 31 2.5 结构化程序设计方法 31 3 数据类型、运算符与表达式 3.1 C语言的数据类型 32 ...
天健医疗HIS系统的数据库表结构说明,再数据分析时可以帮助不了解的数据结构的工程师,快速的了解详细的数据情况。
《数据结构》课程第三次实验报告 实验报告(三) "姓名 " "学号 " "班级 " " "实验名称 "顺序栈的基本操作 "实验日期 " "机房 " " "实验报告 " "1. 说明自己在实验操作过程中遇到的难点及解决方法 " "难点: " "1....