背包、队列、栈（附数据类型实现）

红太狼 2022-06-11 05:50 157阅读 0赞

# 背包、队列和栈 #

背包、队列和栈数据类型都非常基础并且应用广泛。

## API ##

![这里写图片描述][SouthEast]

## 背包 ##

背包是一种不支持从中删除元素的集合数据类型，目的是帮助用例收集元素并迭代所有收集到的元素，也是检查背包是否为空，或者获取背包中元素的数量。

**使用链表实现**

import java.util.Iterator;
    import java.util.NoSuchElementException;
    
    import edu.princeton.cs.algs4.StdIn;
    import edu.princeton.cs.algs4.StdOut;
    
    
    public class Bag<Item> implements Iterable<Item> { 
        private Node<Item> first;    // beginning of bag
        private int n;               // number of elements in bag
    
        // helper linked list class
        private static class Node<Item> { 
            private Item item;
            private Node<Item> next;
        }
    
        /** * Initializes an empty bag. */
        public Bag() {
            first = null;
            n = 0;
        }
    
        /** * Returns true if this bag is empty. * * @return {@code true} if this bag is empty; * {@code false} otherwise */
        public boolean isEmpty() {
            return first == null;
        }
    
        /** * Returns the number of items in this bag. * * @return the number of items in this bag */
        public int size() {
            return n;
        }
    
        /** * Adds the item to this bag. * * @param item the item to add to this bag */
        public void add(Item item) {
            Node<Item> oldfirst = first;
            first = new Node<Item>();
            first.item = item;
            first.next = oldfirst;
            n++;
        }
    
    
        /** * Returns an iterator that iterates over the items in this bag in arbitrary order. * * @return an iterator that iterates over the items in this bag in arbitrary order */
        public Iterator<Item> iterator()  {
            return new ListIterator<Item>(first);  
        }
    
        // an iterator, doesn't implement remove() since it's optional
        private class ListIterator<Item> implements Iterator<Item> { 
            private Node<Item> current;
    
            public ListIterator(Node<Item> first) {
                current = first;
            }
    
            public boolean hasNext()  { return current != null;                     }
            public void remove()      { throw new UnsupportedOperationException();  }
    
            public Item next() {
                if (!hasNext()) throw new NoSuchElementException();
                Item item = current.item;
                current = current.next; 
                return item;
            }
        }
    
        /** * Unit tests the {@code Bag} data type. * * @param args the command-line arguments */
        public static void main(String[] args) {
            Bag<String> bag = new Bag<String>();
            while (!StdIn.isEmpty()) {
                String item = StdIn.readString();
                bag.add(item);
            }
    
            StdOut.println("size of bag = " + bag.size());
            for (String s : bag) {
                StdOut.println(s);
            }
        }
    
    }

## 队列 ##

队列是一种基于先进先出（FIFO）策略的集合类型。在实际应用中使用队列的只要原因是在用集合保存元素的同事保存它们的相对顺序：使他们入列顺序和出列顺序相同。

##### 队列的数据类型实现 #####

**1.常规实现**

package com.founder.zan.impl;
    
    import java.util.Iterator;
    import java.util.NoSuchElementException;
    
    import edu.princeton.cs.algs4.StdIn;
    import edu.princeton.cs.algs4.StdOut;
    public class ResizingArrayQueue<Item> implements Iterable<Item> { 
        private Item[] q;       // 队列元素
        private int n;          // 队列的长度
        private int first;      // index of first element of queue
        private int last;       // index of next available slot
    
    
        /** * 队列初始化 */
        public ResizingArrayQueue() {
            q = (Item[]) new Object[2];
            n = 0;
            first = 0;
            last = 0;
        }
    
        /** * 队列是否为空 * @return true if this queue is empty; false otherwise */
        public boolean isEmpty() {
            return n == 0;
        }
    
        /** * 队列的大小 * @return the number of items in this queue */
        public int size() {
            return n;
        }
    
        // 队列扩容
        private void resize(int capacity) {
            assert capacity >= n;
            Item[] temp = (Item[]) new Object[capacity];
            for (int i = 0; i < n; i++) {
                temp[i] = q[(first + i) % q.length];
            }
            q = temp;
            first = 0;
            last  = n;
        }
    
        /** * 入队 * @param item the item to add */
        public void enqueue(Item item) {
            // double size of array if necessary and recopy to front of array
            if (n == q.length) resize(2*q.length);   // double size of array if necessary
            q[last++] = item;                        // add item
            if (last == q.length) last = 0;          // wrap-around
            n++;
        }
    
        /** * 出队 * @return the item on this queue that was least recently added * @throws java.util.NoSuchElementException if this queue is empty */
        public Item dequeue() {
            if (isEmpty()) throw new NoSuchElementException("Queue underflow");
            Item item = q[first];
            q[first] = null;                            // to avoid loitering
            n--;
            first++;
            if (first == q.length) first = 0;           // wrap-around
            // shrink size of array if necessary
            if (n > 0 && n == q.length/4) resize(q.length/2); 
            return item;
        }
    
        /** * Returns the item least recently added to this queue. * @return the item least recently added to this queue * @throws java.util.NoSuchElementException if this queue is empty */
        public Item peek() {
            if (isEmpty()) throw new NoSuchElementException("Queue underflow");
            return q[first];
        }
    
    
        /** * Returns an iterator that iterates over the items in this queue in FIFO order. * @return an iterator that iterates over the items in this queue in FIFO order */
        public Iterator<Item> iterator() {
            return new ArrayIterator();
        }
    
        // an iterator, doesn't implement remove() since it's optional
        private class ArrayIterator implements Iterator<Item> { 
            private int i = 0;
            public boolean hasNext()  { return i < n;                               }
            public void remove()      { throw new UnsupportedOperationException();  }
    
            public Item next() {
                if (!hasNext()) throw new NoSuchElementException();
                Item item = q[(i + first) % q.length];
                i++;
                return item;
            }
        }
    
       /** * Unit tests the {@code ResizingArrayQueue} data type. * * @param args the command-line arguments */
        public static void main(String[] args) {
            ResizingArrayQueue<String> queue = new ResizingArrayQueue<String>();
            while (!StdIn.isEmpty()) {
                String item = StdIn.readString();
                if (!item.equals("-")) queue.enqueue(item);
                else if (!queue.isEmpty()) StdOut.print(queue.dequeue() + " ");
            }
            StdOut.println("(" + queue.size() + " left on queue)");
        }
    
    }

**2 使用链表实现**

import java.util.Iterator;
    import java.util.NoSuchElementException;
    
    import edu.princeton.cs.algs4.StdIn;
    import edu.princeton.cs.algs4.StdOut;
    
    
    public class Queue<Item> implements Iterable<Item> { 
        private Node<Item> first;    // beginning of queue
        private Node<Item> last;     // end of queue
        private int n;               // number of elements on queue
    
        // helper linked list class
        private static class Node<Item> { 
            private Item item;
            private Node<Item> next;
        }
    
        /** * Initializes an empty queue. */
        public Queue() {
            first = null;
            last  = null;
            n = 0;
        }
    
        /** * Returns true if this queue is empty. * * @return {@code true} if this queue is empty; {@code false} otherwise */
        public boolean isEmpty() {
            return first == null;
        }
    
        /** * Returns the number of items in this queue. * * @return the number of items in this queue */
        public int size() {
            return n;
        }
    
        /** * Returns the item least recently added to this queue. * * @return the item least recently added to this queue * @throws NoSuchElementException if this queue is empty */
        public Item peek() {
            if (isEmpty()) throw new NoSuchElementException("Queue underflow");
            return first.item;
        }
    
        /** * Adds the item to this queue. * * @param item the item to add */
        public void enqueue(Item item) {
            Node<Item> oldlast = last;
            last = new Node<Item>();
            last.item = item;
            last.next = null;
            if (isEmpty()) first = last;
            else           oldlast.next = last;
            n++;
        }
    
        /** * Removes and returns the item on this queue that was least recently added. * * @return the item on this queue that was least recently added * @throws NoSuchElementException if this queue is empty */
        public Item dequeue() {
            if (isEmpty()) throw new NoSuchElementException("Queue underflow");
            Item item = first.item;
            first = first.next;
            n--;
            if (isEmpty()) last = null;   // to avoid loitering
            return item;
        }
    
        /** * Returns a string representation of this queue. * * @return the sequence of items in FIFO order, separated by spaces */
        public String toString() {
            StringBuilder s = new StringBuilder();
            for (Item item : this) {
                s.append(item);
                s.append(' ');
            }
            return s.toString();
        } 
    
        /** * Returns an iterator that iterates over the items in this queue in FIFO order. * * @return an iterator that iterates over the items in this queue in FIFO order */
        public Iterator<Item> iterator()  {
            return new ListIterator<Item>(first);  
        }
    
        // an iterator, doesn't implement remove() since it's optional
        private class ListIterator<Item> implements Iterator<Item> { 
            private Node<Item> current;
    
            public ListIterator(Node<Item> first) {
                current = first;
            }
    
            public boolean hasNext()  { return current != null;                     }
            public void remove()      { throw new UnsupportedOperationException();  }
    
            public Item next() {
                if (!hasNext()) throw new NoSuchElementException();
                Item item = current.item;
                current = current.next; 
                return item;
            }
        }
    
    
        /** * Unit tests the {@code Queue} data type. * * @param args the command-line arguments */
        public static void main(String[] args) {
            Queue<String> queue = new Queue<String>();
            while (!StdIn.isEmpty()) {
                String item = StdIn.readString();
                if (!item.equals("-"))
                    queue.enqueue(item);
                else if (!queue.isEmpty())
                    StdOut.print(queue.dequeue() + " ");
            }
            StdOut.println("(" + queue.size() + " left on queue)");
        }
    }

# 栈 #

下压栈（简称栈）是一种基于先进后出（LIFO）策略的集合类型。

###### 栈的数据类型实现 ######

*  每项操作的用时都与集合大小无关。
 *  空间需求总是不超过集合大小乘以一个常数。

这份泛型的可迭代的Stack API的实现是所有集合类抽象数据类型实现的模板，它讲所有元素保存在数组中，并动态调整数组的大小以保持数组大小和栈大小之比小于一个常数。  
**1常规实现**

import java.util.Iterator;
    import java.util.NoSuchElementException;
    
    import edu.princeton.cs.algs4.StdIn;
    import edu.princeton.cs.algs4.StdOut;
    
    public class ResizingArrayStack<Item> implements Iterable<Item> { 
        private Item[] a;         
        private int n;       //栈的深度
    
        /** * 栈的初始化 */
        public ResizingArrayStack() {
            a = (Item[]) new Object[2];
            n = 0;
        }
    
        /** * 栈是否为空 * @return */
        public boolean isEmpty() {
            return n == 0;
        }
    
        /** * 栈的深度 * @return */
        public int size() {
            return n;
        }
    
    
        // 扩容
        private void resize(int capacity) {
            assert capacity >= n;
    
            // textbook implementation
            Item[] temp = (Item[]) new Object[capacity];
            for (int i = 0; i < n; i++) {
                temp[i] = a[i];
            }
            a = temp;
    
           // alternative implementation
           // a = java.util.Arrays.copyOf(a, capacity);
        }
    
    
    
        /** * 压入一个元素 * @param item the item to add */
        public void push(Item item) {
            if (n == a.length) resize(2*a.length);    // double size of array if necessary
            a[n++] = item;                            // add item
        }
    
        /** * 弹出一个元素. * @return the item most recently added * @throws java.util.NoSuchElementException if this stack is empty */
        public Item pop() {
            if (isEmpty()) throw new NoSuchElementException("Stack underflow");
            Item item = a[n-1];
            a[n-1] = null;                              // to avoid loitering
            n--;
            // shrink size of array if necessary
            if (n > 0 && n == a.length/4) resize(a.length/2);
            return item;
        }
    
    
        /** * 返回当前栈顶元素，但不删除 * @return the item most recently added to this stack * @throws java.util.NoSuchElementException if this stack is empty */
        public Item peek() {
            if (isEmpty()) throw new NoSuchElementException("Stack underflow");
            return a[n-1];
        }
    
        /** * 迭代 * @return an iterator to this stack that iterates through the items in LIFO order. */
        public Iterator<Item> iterator() {
            return new ReverseArrayIterator();
        }
    
        // an iterator, doesn't implement remove() since it's optional
        private class ReverseArrayIterator implements Iterator<Item> { 
            private int i;
    
            public ReverseArrayIterator() {
                i = n-1;
            }
    
            public boolean hasNext() {
                return i >= 0;
            }
    
            public void remove() {
                throw new UnsupportedOperationException();
            }
    
            public Item next() {
                if (!hasNext()) throw new NoSuchElementException();
                return a[i--];
            }
        }
    
    
        /** * 测试 * * @param args the command-line arguments */
        public static void main(String[] args) {
            ResizingArrayStack<String> stack = new ResizingArrayStack<String>();
            while (!StdIn.isEmpty()) {
                String item = StdIn.readString();
                if (!item.equals("-")) stack.push(item);
                else if (!stack.isEmpty()) StdOut.print(stack.pop() + " ");
            }
            StdOut.println("(" + stack.size() + " left on stack)");
        }
    }

**2使用链表实现**

import java.util.Iterator;
    import java.util.NoSuchElementException;
    
    import edu.princeton.cs.algs4.StdIn;
    import edu.princeton.cs.algs4.StdOut;
    
    
    public class Stack<Item> implements Iterable<Item> { 
        private Node<Item> first;     // top of stack
        private int n;                // size of the stack
    
        // helper linked list class
        private static class Node<Item> { 
            private Item item;
            private Node<Item> next;
        }
    
        /** * Initializes an empty stack. */
        public Stack() {
            first = null;
            n = 0;
        }
    
        /** * Returns true if this stack is empty. * * @return true if this stack is empty; false otherwise */
        public boolean isEmpty() {
            return first == null;
        }
    
        /** * Returns the number of items in this stack. * * @return the number of items in this stack */
        public int size() {
            return n;
        }
    
        /** * Adds the item to this stack. * * @param item the item to add */
        public void push(Item item) {
            Node<Item> oldfirst = first;
            first = new Node<Item>();
            first.item = item;
            first.next = oldfirst;
            n++;
        }
    
        /** * Removes and returns the item most recently added to this stack. * * @return the item most recently added * @throws NoSuchElementException if this stack is empty */
        public Item pop() {
            if (isEmpty()) throw new NoSuchElementException("Stack underflow");
            Item item = first.item;        // save item to return
            first = first.next;            // delete first node
            n--;
            return item;                   // return the saved item
        }
    
    
        /** * Returns (but does not remove) the item most recently added to this stack. * * @return the item most recently added to this stack * @throws NoSuchElementException if this stack is empty */
        public Item peek() {
            if (isEmpty()) throw new NoSuchElementException("Stack underflow");
            return first.item;
        }
    
        /** * Returns a string representation of this stack. * * @return the sequence of items in this stack in LIFO order, separated by spaces */
        public String toString() {
            StringBuilder s = new StringBuilder();
            for (Item item : this) {
                s.append(item);
                s.append(' ');
            }
            return s.toString();
        }
    
    
        /** * Returns an iterator to this stack that iterates through the items in LIFO order. * * @return an iterator to this stack that iterates through the items in LIFO order */
        public Iterator<Item> iterator() {
            return new ListIterator<Item>(first);
        }
    
        // an iterator, doesn't implement remove() since it's optional
        private class ListIterator<Item> implements Iterator<Item> { 
            private Node<Item> current;
    
            public ListIterator(Node<Item> first) {
                current = first;
            }
    
            public boolean hasNext() {
                return current != null;
            }
    
            public void remove() {
                throw new UnsupportedOperationException();
            }
    
            public Item next() {
                if (!hasNext()) throw new NoSuchElementException();
                Item item = current.item;
                current = current.next; 
                return item;
            }
        }
    
    
        /** * Unit tests the {@code Stack} data type. * * @param args the command-line arguments */
        public static void main(String[] args) {
            Stack<String> stack = new Stack<String>();
            while (!StdIn.isEmpty()) {
                String item = StdIn.readString();
                if (!item.equals("-"))
                    stack.push(item);
                else if (!stack.isEmpty())
                    StdOut.print(stack.pop() + " ");
            }
            StdOut.println("(" + stack.size() + " left on stack)");
        }
    }

待完善。  
jar包下载：  
资源来自：[http://algs4.cs.princeton.edu/home/][http_algs4.cs.princeton.edu_home]

[SouthEast]: /images/20220611/391943f4387c44299c82d6ac1c252114.png
[http_algs4.cs.princeton.edu_home]: http://algs4.cs.princeton.edu/home/