我们说下上述三者的数据结构和基本的Java实现
1.背包
背包不支持从中删除元素的集合数据类型,而且无序(类似一个袋子里有很多东西,我们可以在其中找某个东西,但是每次打开发现里面东西顺序都不一样)
2.下压栈(简称 ‘栈’)的介绍
基于后进先出,形象化的来说,就是我们在桌子上进行摞书,
超链接也是如此,我们可以不断的点击超链接访问新网页,但是可以利用”回退”功能去返回之前的网页
后进先出,就是优先服务等待时间最短的
3.先进先出的队列的介绍
内部维护一个队列,优先服务等待时间最久的人,保存数据结构的同事,保存对应的相对顺序
三者常见的API如下
顺路说一下,迭代相关的解释
对于迭代,就是通过foreach语句,迭代遍历每一个元素
常见的,可以使用iterator()方法并且返回Iterator对象
Iterator对象必须包含两个方法:
hasNext()返回布尔值 next()返回泛型
我们来尝试使用链表,来实现上述的几种数据结构
链表是一种支持递归的数据结构,可以指向其他节点node的引用
常见的单向链表的类如下
private class Node{
Item item;
Node next;
}
利用上述的方式,我们将链表联系起来
如果我们想要插入结点,在链表的首位可以这么做:
first保存在oldfirst中,然后新创建一个首结点,并且指向oldfirst
首位删除则更加简单:
first = first.next();
在尾部添加一个结点,流程基本为 保存原来尾部结点,然后创建新的尾部结点,将尾链指向新的结点(谨慎!)如果链表只有一个结点,就会影响首尾,链表为空也无法处理
为了可以直接删除最后一个节,那么还有着双向链表的数据结构
(1)链表实现栈
| public class Stack<Item> {
private Node first; private int N;//元素的数量 private class Node{ Item item; Node next;//栈的位置 }//开始实现常见方法 public boolean isEmpty() {//是否为空 return first == null; } public int size() {//查看元素数值 return N; } public void push(Item item) {//添加元素 Node usdNode = first;//第一转为之前的第一 first = new Node(); first.item = item;//导入item first.next = usdNode; N++; } public Item pop() { Item item = first.item;//导出数据 first = first.next; N–; return item; } //缺点:没及时的对游离数据进行回收 } |
使用链表实现队列
| public class Queue<Item> {//使用了泛型的概念
private Node start;//开始位和结束位 private Node end; private int N;//元素的数量 private class Node{ Item item; Node next;//栈的位置,也是一个实例变量 } public boolean isEmpty() {//两个常用方法 return N==0; } public int size() { return N; } public void enqueue(Item item) {//设置添加方法 Node oldend = end; end.item = item; end.next = null;//从尾端插入 if (isEmpty()) { start = end; }else { oldend.next = end; } N++; } public Item dequeue() { Item item = start.item; start = start.next; //从开头段删除 if (isEmpty()) { end = null; } N–; return item; } } |
最后就是背包的实现,我们实现了一个迭代器,方便链表的使用
| public class Bag<Item> implements Iterable<Item>{
private Node Start; private int N; private class Node{ Item item; Node next; } public boolean isEmpty() { return N==0; } public int size() { return N; } public void add(Item item) { Node oldNode = Start; Start.item = item;//写入新的 Start.next = oldNode; N++; } public Iterator<Item> iterator() { // TODO Auto-generated method stub return new BagIterator(); } public class BagIterator implements Iterator<Item>{ private Node current = Start;//导入Node @Override public boolean hasNext() { return current != null; } @Override public Item next() { Item item = current.item; current = current.next; return item; } } } |