栈（Stack）、队列（Queue）与包（Bag）的实现

骑猪看日落 2022-07-18 01:13 167阅读 0赞

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

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;
        }
    }

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