美文网首页
java版栈和队列之数组和链表实现(实现Iterable可迭代版

java版栈和队列之数组和链表实现(实现Iterable可迭代版

作者: progressin_2240 | 来源:发表于2018-02-01 00:08 被阅读0次

    本章内容主要来自算法(第四版) Robert Sedgewick著 1.3小节

    栈(后进先出)的基本功能

    public class Stack<Item> implements Iterable<Item>{
       Stack()
       void push(Item)
       Item pop()
       boolean isEmpty()
       int size()
    }
    

    队列(先进先出):

    public class Queue<Item> implements Iterable<Item>{
        Queue()
        void enqueue(Item item)
        Item deque()
        boolean isEmpty()
        int size()
    }
    

    关于Iterable和Iterator:

    interface      method
    java.lang.Iterable => iterator()
    java.util.Iterator => hasNext()、next()、remove()

    foreach实质

      Stack<String> collection = new Stack<String>();
      ...
      for(String s : collection){
          System.out.println(s);
      }
      ...
      等价于如下代码=======================================
      Iterator<String> i = collection.iterator();
      while(i.hasNext()){
          System.out.println(i.next());
      }
    

    所以实现Iterable需实现Iterator()方法,返回的是实现java.util.Iterator接口的内部类对象,注意内部类可以访问外部类实例域
    数组没有实现该接口也能使用foreach,留待后答

    数组版栈实现

    import java.util.Iterator;
    
    public class Test {
        public static void main(String[] args) {
    
        }
    }
    //未重写toString()等方法
    class Stack<T> implements Iterable<T>{
        private int N =0;
        private T[] t;
        public Stack() {
            t = (T[])new Object[8];   //此处将默认设为8
        }
        public Stack(int length) {
            t = (T[])new Object[length];   //此处将默认设为8
        }
        private void resize(int length) {
            //将栈移动到一个长度为length的新数组
            T[] temp = (T[])new Object[length];
            for(int i=0;i<N;i++) {
                temp[i] = t[i];
            }
            t = temp;
        }
        public void push(T element) {
            if(N==t.length) {
                resize(2*t.length+2);
            }
            t[N++] = element;
        }
        public T pop() {
            T a = null;
            if(N>0){
                a=t[--N];
                t[N]=null;
                if(N>8&&N<t.length/4){
                    resize(t.length/2);
                }
            }
            return a;
                
            
        }
        public boolean isEmpty() {
            return N==0;
        }
        public int size() {
            return N;
        }
        @Override
        public Iterator<T> iterator() {
            return new ReverseArrayIterator();
        }
        //JDK 1.8不用覆盖remove()方法了
        private class ReverseArrayIterator implements Iterator<T>{
            private int i = N;
            @Override
            public boolean hasNext() {
                return i > 0;
            }
            @Override
            public T next() {
                return t[--i];
            }
        }
    }
    

    链表版栈实现

    class Stack<T> implements Iterable<T>{
        private Node first;
        private int N;
        private class Node{
            T element;
            Node next;
        }
        public boolean isEmpty(){
            return N==0;
        }
        public int size(){
            return N;
        }
        public void push(T element){
            Node oldfirst = first;
            first = new Node();
            first.element = element;
            first.next = oldfirst;
            N++;
        }
        public T pop(){
            //未显示考虑栈为空的状态
            T element = first.element;
            first = first.next;
            N--;
            return element;
        }
        @Override
        public Iterator<T> iterator() {
            return new ListIterator();
        }
        private class ListIterator implements Iterator<T>{
            private Node current = first;
            @Override
            public boolean hasNext() {
                return current != null;
            }
    
            @Override
            public T next() {
                T element = current.element;
                current = current.next;
                return element;
            }
            
        }
    }
    

    数组版队列实现

    import java.util.Iterator;
    
    public class Test {
        public static void main(String[] args) {
    
        }
    }
    //循环列表
    class Queue<T> implements Iterable<T>{
        private int head;
        private int tail;
        private int N;
        T[] t;
        public Queue(){
            N = 0;
            head = 0;
            tail = 0;
            t = (T[])new Object[8];
        }
        public Queue(int length){
            N = 0;
            head = 0;
            tail = 0;
            t = (T[])new Object[length];
        }
        public void enqueue(T element){
            if(N<t.length){
                if(N==0){
                    t[head]=element;
                }
                else{
                    tail = (++tail) % t.length;
                    t[tail] = element;
                }
                N++;
            }
            else{
                //队列已满
            }
        }
        public void dequeue(){
            if(N>0){
                //N=1说明首尾指向同一位
                if(N==1){
                    t[head]=null;
                    N--;
                }
                else{
                    //为null防止对象游离
                    t[head]=null;
                    head = (++head)%t.length;
                    N--;
                }
            }
            else{
                //队列为空
            }
        }
        public int size(){
            return N;
            
        }
        
        @Override
        public Iterator<T> iterator() {
            return new FirstinfirstoutArrayIterator();
        }
        private class FirstinfirstoutArrayIterator implements Iterator<T>{
            private int i = 0;
            @Override
            public boolean hasNext() {
                return i < N;
            }
            @Override
            public T next() {
                T element = t[(i+head)%t.length];    //从头元素开始获取元素.
                i++;
                return element;
            }
        }
    }
    

    链表版队列实现

    import java.util.Iterator;
    
    public class Test {
        public static void main(String[] args) {
    
        }
    }
    class Queue<T> implements Iterable<T>{
        private Node first;
        private Node last;
        private int N;
        private class Node{
            T element;
            Node next;
        }
        public boolean isEmpty(){
            return first == null;
        }
        public int size(){
            return N;
        }
        public void enqueue(T element){
            Node oldlast = last;
            last = new Node();
            last.element = element;
            last.next = null;
            if(isEmpty()) first = last;
            else oldlast.next = last;
            N++;
        }
        public T dequeue(){
            if(isEmpty()){
                first = null;
                last = null;
                return null;
            }
            T element = first.element;
            first = first.next;
            N--;
            if(N==0){
                first = null;
                last = null;
            }
            return element;
        }
        @Override
        public Iterator<T> iterator() {
            return new ListIterator();
        }
        private class ListIterator implements Iterator<T>{
            private Node current = first;
            @Override
            public boolean hasNext() {
                return current != null;
            }
    
            @Override
            public T next() {
                T element = current.element;
                current = current.next;
                return element;
            }
            
        }
    }
    

    java中不允许泛型数组,需要类型转换例如 a=(Type[])new Object[N]

    相关文章

      网友评论

          本文标题:java版栈和队列之数组和链表实现(实现Iterable可迭代版

          本文链接:https://www.haomeiwen.com/subject/tamlzxtx.html