栈(Stack)、队列(Queue)与包(Bag)的实现

时间:2021-01-22 17:37:42

使用基本的链表结构实现栈,队列和包三种数据结构。首先用一个嵌套类来定义结点的抽象数据类型:

private class Node{
Item item;
Node next;
}

(1)堆栈Stack

import java.util.Iterator;
public class Stack<Item> implements Iterable<Item>{
private Node first;//栈顶
private int N;//元素数量
private class Node{
Item item;
Node next;
}
public void push(Item item){
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
N++;
}
public Item pop(){
Item item = first.item;
first = first.next;
N--;
return item;
}
//实现迭代
public Iterator<Item> iterator(){
return new ListIterator();
}
private class ListIterator implements Iterator<Item>{
private Node current = first;
public boolean hasNext(){
return current != null;
}
public void remove(){}
public Item next(){
Item item = current.item;
current = current.next;;
return item;
}
}
}

(2)队列(Queue)的实现

public class Queue<Item> implements Iterator<Item>{
private Node first;
private Node last;
private int N;
private class Node{
Item item;
Node next;
}
//队列向队尾填加元素
public void enqueue(Item item){
Node oldlast = last;
last = new Node();
last.item = item;
last.next = null;
if(isEmpty) first = last;
else oldlast.next = last;
N++;
return item;
}
public Item dequeue(){
Item item = first.item;
first = first.next;
if(isEmpty()) last = null;
N--;
return item;
}
}

(3)包(Bag)

public class Bag<Item>{
private Node first;
private int N;
private class Node{
Item item;
Node next;
}
public void add(Item item){
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfiirst;
}
}

顺序存储结构:数组
优点:通过索引可以任意访问元素
缺点:初始化时需要知道元素数量
链式存储结构:链表
优点:使用的空间大小和元素数量成正比
缺点:需要通过引用访问任意元素