算法-基本数据结构

基本数据结构

数组

链表

链表的节点表示

public class Node<Item>{
    Item item;
    Node next;
 }

栈

用链表实现栈

public class Stack<Item> implements Iterable<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 oldfirst=first;
        first=new Node();
        first.item=item;
        first.next=oldfirst;
        N++;
    }
    //出栈
    public Item pop(){
        if(isEmpty()){
            try {
                throw new Exception("stack is empty");
            } catch (Exception e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }
        Item item=first.item;
        first=first.next;
        N--;
        return item;
    }
    public Iterator<Item> iterator(){
        return new Iterator<Item>(){
            private Node current=first;
            @Override                
            public boolean hasNext(){
                return current!=null;
            } 
            @Override
            public Item next(){
                Item item=current.item;
                current=current.next;
                return item;
            }    
            public void remove(){}
        };
    }    
}

队列

用链表实现队列

public class Queue<Item> implements Iterable<Item> {
    private Node first;
    private Node last;
    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 oldlast=last;
        last=new Node();
        last.item=item;
        last.next=null;
        if(isEmpty()){
            first=last;
        }else{
            oldlast.next=last;
        }
        N++;
    }
    //出队
    public Item dequeue(){
        if(isEmpty()){
            try {
                throw new Exception("queue is empty");
            } catch (Exception e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }
        Item item=first.item;
        first=first.next;
        N--;
        if(isEmpty()){
            last=null;
        }
        return item;
    }
    public Iterator<Item> iterator(){
        return new Iterator<Item>(){
            private Node current=first;
            @Override                
            public boolean hasNext(){
                return current!=null;
            } 
            @Override
            public Item next(){
                Item item=current.item;
                current=current.next;
                return item;
            }    
            public void remove(){}
        };
    }        
}