温习Algs4 (一):背包, 栈, 队列和线性表

男娘i 2022-04-13 11:22 216阅读 0赞

### 背包, 栈, 队列和线性表 ###

*  背包
 *   *  Bag.java
     *  复杂度分析
 *  栈
 *   *  Stack.java
     *  复杂度分析
 *  队列
 *   *  Queue.java
     *  复杂度分析
 *  线性表
 *   *  Vector.java
     *  复杂度分析
 *  总结

# 背包 #

背包是最简单的数据结构, 只有**添加数据**和**遍历元素**两个功能, 内部实现是链表.

## Bag.java ##

/****************************************************************************** * Compilation: javac Bag.java * Execution: java Bag * Author: Chenghao Wang ******************************************************************************/
    
    import java.util.Iterator;
    import java.util.NoSuchElementException;
    
    public class Bag<T> implements Iterable<T> { 
    
        private class Node { 
            private T item;
            private Node next;
    
            Node(T item) { 
                this.item = item;
                next = null;
            }
        }
    
        private class BagIterator implements Iterator<T> { 
    
            private Node current = head;
    
            @Override
            public boolean hasNext() { 
                return current != null;
            }
    
            @Override
            public T next() { 
                if (current == null) throw new NoSuchElementException();
                T result = current.item;
                current = current.next;
                return result;
            }
    
            @Override
            public void remove() { 
                throw new UnsupportedOperationException();
            }
        }
    
        private Node head = null;
    
        public void add(T item) { 
            Node n = new Node(item);
            n.next = head;
            head = n;
        }
    
        @Override
        public Iterator<T> iterator() { 
            return new BagIterator();
        }
    }

## 复杂度分析 ##

*  add: *O(1)*

# 栈 #

栈支持的功能有压栈, 出栈, 查询栈顶元素, 检查是否为空和查询元素个数. 内部实现也是链表.

## Stack.java ##

/****************************************************************************** * Compilation: javac Stack.java * Execution: java Stack * Author: Chenghao Wang ******************************************************************************/
    
    import java.util.Iterator;
    import java.util.NoSuchElementException;
    
    public class Stack<T> implements Iterable<T> { 
    
        private class Node { 
            private T item;
            private Node next;
    
            Node(T item) { 
                this.item = item;
                next = null;
            }
        }
    
        private class StackIterator implements Iterator<T> { 
            private Node current = head;
    
            @Override
            public boolean hasNext() { 
                return current != null;
            }
    
            @Override
            public T next() { 
                if (current == null) throw new NoSuchElementException();
                T result = current.item;
                current = current.next;
                return result;
            }
    
            @Override
            public void remove() { 
                throw new UnsupportedOperationException();
            }
        }
    
        private Node head = null;
        private int size = 0;
    
        public void push(T item) { 
            Node n = new Node(item);
            n.next = head;
            head = n;
            size++;
        }
    
        public T pop() { 
            if (size == 0) { 
                throw new NoSuchElementException();
            }
    
            size--;
            T result = head.item;
            head = head.next;
            return result;
        }
    
        public T top() { 
            if (size == 0) { 
                throw new NoSuchElementException();
            }
            return head.item;
        }
    
        public boolean isEmpty() { 
            return size == 0;
        }
    
        public int size() { 
            return size;
        }
    
        public Iterator<T> iterator() { 
            return new StackIterator();
        }
    }

## 复杂度分析 ##

*  push: *O(1)*
 *  pop: *O(1)*
 *  isEmpty: *O(1)*
 *  size: *O(1)*

# 队列 #

队列支持的功能有入列, 出列, 检查是否为空和查询元素个数. 内部实现也是链表.

## Queue.java ##

/****************************************************************************** * Compilation: javac Queue.java * Execution: java Queue * Author: Chenghao Wang ******************************************************************************/
    
    import java.util.NoSuchElementException;
    import java.util.Iterator;
    
    public class Queue<T> implements Iterable<T> { 
    
        private class Node { 
            private T item;
            private Node next;
    
            Node(T item) { 
                this.item = item;
                next = null;
            }
        }
    
        private class QueueIterator implements Iterator<T> { 
            private Node current = head;
    
            public boolean hasNext() { 
                return current != null;
            }
    
            public T next() { 
                if (current == null) throw new NoSuchElementException();
                T result = current.item;
                current = current.next;
                return result;
            }
    
            public void remove() { 
                throw new UnsupportedOperationException();
            }
        }
    
        private Node head = null;
        private Node tail = null;
        private int size = 0;
    
        public void enqueue(T item) { 
            Node n = new Node(item);
            if (head == null) head = n;
            else tail.next = n;
            tail = n;
            size++;
        }
    
        public T dequeue() { 
            if (size == 0) { 
                throw new NoSuchElementException();
            }
    
            size--;
            T result = head.item;
            head = head.next;
            return result;
        }
    
        public boolean isEmpty() { 
            return size == 0;
        }
    
        public int size() { 
            return size;
        }
    
        public Iterator<T> iterator() { 
            return new QueueIterator();
        }
    }

## 复杂度分析 ##

*  enqueue: *O(1)*
 *  dequeue: *O(1)*
 *  isEmpty: *O(1)*
 *  size: *O(1)*

# 线性表 #

线性表即为动态数组, 支持的方法是对元素的增删查改, 查询是否为空和元素个数.

## Vector.java ##

/****************************************************************************** * Compilation: javac Vector.java * Execution: java Vector * Author: Chenghao Wang ******************************************************************************/
    
    import java.util.Iterator;
    import java.util.NoSuchElementException;
    
    public class Vector<T> implements Iterable<T> { 
    
        private class VectorIterator implements Iterator<T> { 
    
            private int ptr = 0;
    
            @Override
            public boolean hasNext() { 
                return ptr < size;
            }
    
            @Override
            public T next() { 
                if (ptr >= size) { 
                    throw new NoSuchElementException();
                }
    
                return content[ptr++];
            }
    
            @Override
            public void remove() { 
                throw new UnsupportedOperationException();
            }
        }
    
        private static final int INITIAL_CAPACITY = 8;
        private int capacity;
        private int size;
        private T[] content;
    
        Vector() { 
            content = (T[]) new Object[INITIAL_CAPACITY];
            capacity = INITIAL_CAPACITY;
            size = 0;
        }
    
        void insert(int index, T item) { 
            if ((index < 0) || (index > size)) { 
                throw new IllegalArgumentException();
            }
    
            size++;
            for (int i = size - 1; i > index; i++) { 
                content[i] = content[i - 1];
            }
    
            content[index] = item;
            
            if (size == capacity) { 
                resize(capacity * 2);
            }
        }
    
        void add(T item) { 
            insert(size, item);
        }
    
        void remove(int index) { 
            if ((index < 0) || (index >= size)) { 
                throw new IllegalArgumentException();
            }
    
            size--;
    
            for (int i = index; i < size; i++) { 
                content[i] = content[i+1];
            }
    
            if ((size < (capacity / 8)) && (size > 1)) { 
                resize(capacity / 4);
            }
        }
    
        T get(int index) { 
            if ((index < 0) || (index >= size)) { 
                throw new IllegalArgumentException();
            }
    
            return content[index];
        }
    
        void set(int index, T item) { 
            if ((index < 0) || (index >= size)) { 
                throw new IllegalArgumentException();
            }
    
            content[index] = item;
        }
    
        void resize(int c) { 
            capacity = c;
            T[] newContent = (T[]) new Object[capacity];
            for (int i = 0; i < size; i++) { 
                newContent[i] = content[i];
            }
            content = newContent;
        }
    
        boolean isEmpty() { 
            return size == 0;
        }
    
        int size() { 
            return size;
        }
    
        @Override
        public Iterator<T> iterator() { 
            return new VectorIterator();
        }
    }

## 复杂度分析 ##

*  add: *O(1)*
 *  insert: *O(n)*
 *  remove: *O(n)*
 *  set: *O(1)*
 *  isEmpty: *O(1)*
 *  size: *O(1)*

# 总结 #

最近打算重新复习和巩固一下基础算法, 先从最基本的数据结构入手, 将Algorithms 4th Ed. 的所有算法和数据结构重新实现一遍.