背包：

它是一种不支持从中删除元素的集合数据类型，目标就是帮助收集全部的元素，并且迭代遍历所有收集到的元素。迭代的顺序不确定，并且与用例无关。

主要的API：

　　　　　　Bag()  　　　　   　　 　　创建一个空的背包

void 　   　  add(Item item)　　　　　添加一个元素

boolean　　 isEmpty()　　　　　　　　判断是否为空

int 　　　　 size()　　　　　　　　　　 背包中的数量

java实现：

链表：

1. import java.util.Iterator;
2. import java.util.NoSuchElementException;
4. public class Bag<Item> implements Iterable<Item> {
5.      // 背包的两个属性，一个是背包里面的数量，一个是背包里面的节点
6.      private int N;
7.      private Node<Item> first;
9.      private static class Node<Item> {
10.           private Item item;
11.           private Node<Item> next;
12.      }
14.      // 构造一个空的背包
15.      public Bag() {
16.           first = null;
17.           N = 0;
18.      }
20.      // 判断背包是否为空
21.      public boolean isEmpty() {
22.           return first == null;
23.      }
25.      // 背包的数量
26.      public int size() {
27.           return N;
28.      }
30.      // 背包的添加
31.      public void add(Item item) {
32.           Node<Item> oldfirst = first;
33.           first = new Node<Item>();
34.           first.item = item;
35.           first.next = oldfirst;
36.           N++;
37.      }
39.      // 实现迭代器接口的重写
40.      @Override
41.      public Iterator<Item> iterator() {
42.           return new ListIterator<Item>(first);
43.      }
45.      // 构建迭代器对象
46.      private class ListIterator<Item> implements Iterator<Item> {
47.           // 迭代器里面有一个属性节点
48.           private Node<Item> current;
50.           // 构造器
51.           public ListIterator(Node<Item> first) {
52.                current = first;
53.           }
55.           // 判断是否迭代完成
56.           public boolean hasNext() {
57.                return current != null;
58.           }
60.           // 移除
61.           public void remove() {
62.                throw new UnsupportedOperationException();
63.           }
65.           // 迭代下一个
66.           public Item next() {
67.                if (!hasNext())
68.                     throw new NoSuchElementException();
69.                Item item = current.item;
70.                current = current.next;
71.                return item;
72.           }
73.      }
75.      public static void main(String[] args) {
76.           Bag<String> bag = new Bag<String>();
77.           bag.add("aaa");
78.           bag.add("iii");
79.           for (String s : bag) {
80.                System.out.println(s);
81.           }
82.      }
83. }

可变数组实现：

1. import java.util.Iterator;
2. import java.util.NoSuchElementException;
6. public class ResizingArrayBag<Item> implements Iterable<Item> {
7.     private Item[] a;         // 空数组
8.     private int N = 0;        // 背包元素数量
10.     /**
11.      * 创建一个空的背包
12.      */
13.     public ResizingArrayBag() {
14.         a = (Item[]) new Object[2];
15.     }
17.     /**
18.      * 背包是否为空
19.      * @return true 背包为空; false 相反
20.      */
21.     public boolean isEmpty() {
22.         return N == 0;
23.     }
25.     /**
26.      * 返回背包元素数量
27.      * @return the number of items in this bag
28.      */
29.     public int size() {
30.         return N;
31.     }
33.     // 创建一个数组，大小为capacity
34.     private void resize(int capacity) {
35.         assert capacity >= N;
36.         Item[] temp = (Item[]) new Object[capacity];
37.         for (int i = 0; i < N; i++)
38.             temp[i] = a[i];
39.         a = temp;
40.     }
42.     /**
43.      * 给背包中添加元素
44.      * @param item the item to add to this bag
45.      */
46.     public void add(Item item) {
47.         if (N == a.length) resize(2*a.length);    // 如果N的数量等于给定数组大小的话就重新创建一个数组并且数组大小扩大一倍
48.         a[N++] = item;                            // 增加元素
49.     }
52.     /**
53.      * Returns an iterator that iterates over the items in the bag in arbitrary order.
54.      * @return an iterator that iterates over the items in the bag in arbitrary order
55.      */
56.     public Iterator<Item> iterator() {
57.         return new ArrayIterator();
58.     }
60.     // an iterator, doesn't implement remove() since it's optional
61.     private class ArrayIterator implements Iterator<Item> {
62.         private int i = 0;
63.         public boolean hasNext()  { return i < N;                               }
64.         public void remove()      { throw new UnsupportedOperationException();  }
66.         public Item next() {
67.             if (!hasNext()) throw new NoSuchElementException();
68.             return a[i++];
69.         }
70.     }
72.     /**
73.      * Unit tests the <tt>ResizingArrayBag</tt> data type.
74.      */
75.     public static void main(String[] args) {
76.         ResizingArrayBag<String> bag = new ResizingArrayBag<String>();
77.         bag.add("Hello");
78.         bag.add("World");
79.         bag.add("how");
80.         bag.add("are");
81.         bag.add("you");
83.         for (String s : bag)
84.             StdOut.println(s);
85.     }
87. }

可以用来统计数字来进行计算。

=============================================================================

队列：

全称先进先出队列，按照任务产生的顺序完成他们的策略，基本上每天都会用到：典型就是排队。服务优先等待最久的人。

主要的API：

　　　　　　     Queue()  　　　　   　　 　　创建一个空的队列

void 　   　   enqueue(Item item)　　       添加一个元素

Item              dequeue()                             删除最早添加的元素

boolean　　 isEmpty()　　　　　　　　    判断是否为空

int 　　　　   size()　　　　　　　　　　    队列中的数量 

java代码实现：

链表：

1. import java.util.Iterator;
2. import java.util.NoSuchElementException;
4. public class LinkedQueue<Item> implements Iterable<Item> {
5.      private int N; // 队列元素的数量
6.      private Node first; // 第一个进去的元素
7.      private Node last; // 最后一个进去的元素
9.      // 链表类
10.      private class Node {
11.           private Item item;
12.           private Node next;
13.      }
15.      /**
16.       * 创建一个空的链表
17.       */
18.      public LinkedQueue() {
19.           first = null;
20.           last = null;
21.           N = 0;
22.           assert check();
23.      }
25.      /**
26.       * 判断链表是否为空
27.       * 
28.       * @return true if this queue is empty; false otherwise
29.       */
30.      public boolean isEmpty() {
31.           return first == null;
32.      }
34.      /**
35.       * 返回链表的数量
36.       * 
37.       * @return the number of items in this queue
38.       */
39.      public int size() {
40.           return N;
41.      }
43.      /**
44.       * 返回最近添加的元素
45.       * 
46.       * @return the item least recently added to this queue
47.       * @throws java.util.NoSuchElementException
48.       *             if this queue is empty
49.       */
50.      public Item peek() {
51.           if (isEmpty())
52.                throw new NoSuchElementException("Queue underflow");
53.           return first.item;
54.      }
56.      /**
57.       * 添加一个元素到队列中
58.       * 
59.       * @param item
60.       *            the item to add
61.       */
62.      public void enqueue(Item item) {
63.           Node oldlast = last;
64.           last = new Node();
65.           last.item = item;
66.           last.next = null;
67.           if (isEmpty())
68.                first = last;
69.           else
70.                oldlast.next = last;
71.           N++;
72.           assert check();
73.      }
75.      /**
76.       * 删除队列的第一个元素
77.       * 
78.       * @return the item on this queue that was least recently added
79.       * @throws java.util.NoSuchElementException
80.       *             if this queue is empty
81.       */
82.      public Item dequeue() {
83.           if (isEmpty())
84.                throw new NoSuchElementException("Queue underflow");
85.           Item item = first.item;
86.           first = first.next;
87.           N--;
88.           if (isEmpty())
89.                last = null; // to avoid loitering
90.           assert check();
91.           return item;
92.      }
94.      /**
95.       * 返回一个字符串这个队列的全部元素组成的
96.       * 
97.       * @return the sequence of items in FIFO order, separated by spaces
98.       */
99.      public String toString() {
100.           StringBuilder s = new StringBuilder();
101.           for (Item item : this)
102.                s.append(item + " ");
103.           return s.toString();
104.      }
106.      // check internal invariants
107.      private boolean check() {
108.           if (N == 0) {
109.                if (first != null)
110.                     return false;
111.                if (last != null)
112.                     return false;
113.           } else if (N == 1) {
114.                if (first == null || last == null)
115.                     return false;
116.                if (first != last)
117.                     return false;
118.                if (first.next != null)
119.                     return false;
120.           } else {
121.                if (first == last)
122.                     return false;
123.                if (first.next == null)
124.                     return false;
125.                if (last.next != null)
126.                     return false;
128.                // check internal consistency of instance variable N
129.                int numberOfNodes = 0;
130.                for (Node x = first; x != null; x = x.next) {
131.                     numberOfNodes++;
132.                }
133.                if (numberOfNodes != N)
134.                     return false;
136.                // check internal consistency of instance variable last
137.                Node lastNode = first;
138.                while (lastNode.next != null) {
139.                     lastNode = lastNode.next;
140.                }
141.                if (last != lastNode)
142.                     return false;
143.           }
145.           return true;
146.      }
148.      /**
149.       * Returns an iterator that iterates over the items in this queue in FIFO
150.       * order.
151.       * 
152.       * @return an iterator that iterates over the items in this queue in FIFO
153.       *         order
154.       */
155.      public Iterator<Item> iterator() {
156.           return new ListIterator();
157.      }
159.      // an iterator, doesn't implement remove() since it's optional
160.      private class ListIterator implements Iterator<Item> {
161.           private Node current = first;
163.           public boolean hasNext() {
164.                return current != null;
165.           }
167.           public void remove() {
168.                throw new UnsupportedOperationException();
169.           }
171.           public Item next() {
172.                if (!hasNext())
173.                     throw new NoSuchElementException();
174.                Item item = current.item;
175.                current = current.next;
176.                return item;
177.           }
178.      }
180. }

数组：

 

1. import java.util.Iterator;
2. import java.util.NoSuchElementException;
4. public class ResizingArrayQueue <Item> implements Iterable<Item>{
5.      private Item[] q; // queue elements
6.      private int N = 0; // number of elements on queue
7.      private int first = 0; // index of first element of queue
8.      private int last = 0; // index of next available slot
10.      /**
11.       * Initializes an empty queue.
12.       */
13.      public ResizingArrayQueue() {
14.           // cast needed since no generic array creation in Java
15.           q = (Item[]) new Object[2];
16.      }
18.      /**
19.       * Is this queue empty?
20.       * 
21.       * @return true if this queue is empty; false otherwise
22.       */
23.      public boolean isEmpty() {
24.           return N == 0;
25.      }
27.      /**
28.       * Returns the number of items in this queue.
29.       * 
30.       * @return the number of items in this queue
31.       */
32.      public int size() {
33.           return N;
34.      }
36.      // resize the underlying array
37.      private void resize(int max) {
38.           assert max >= N;
39.           Item[] temp = (Item[]) new Object[max];
40.           for (int i = 0; i < N; i++) {
41.                temp[i] = q[(first + i) % q.length];
42.           }
43.           q = temp;
44.           first = 0;
45.           last = N;
46.      }
48.      /**
49.       * Adds the item to this queue.
50.       * 
51.       * @param item
52.       *            the item to add
53.       */
54.      public void enqueue(Item item) {
55.           // double size of array if necessary and recopy to front of array
56.           if (N == q.length)
57.                resize(2 * q.length); // double size of array if necessary
58.           q[last++] = item; // add item
59.           if (last == q.length)
60.                last = 0; // wrap-around
61.           N++;
62.      }
64.      /**
65.       * Removes and returns the item on this queue that was least recently added.
66.       * 
67.       * @return the item on this queue that was least recently added
68.       * @throws java.util.NoSuchElementException
69.       *             if this queue is empty
70.       */
71.      public Item dequeue() {
72.           if (isEmpty())
73.                throw new NoSuchElementException("Queue underflow");
74.           Item item = q[first];
75.           q[first] = null; // to avoid loitering
76.           N--;
77.           first++;
78.           if (first == q.length)
79.                first = 0; // wrap-around
80.           // shrink size of array if necessary
81.           if (N > 0 && N == q.length / 4)
82.                resize(q.length / 2);
83.           return item;
84.      }
86.      /**
87.       * Returns the item least recently added to this queue.
88.       * 
89.       * @return the item least recently added to this queue
90.       * @throws java.util.NoSuchElementException
91.       *             if this queue is empty
92.       */
93.      public Item peek() {
94.           if (isEmpty())
95.                throw new NoSuchElementException("Queue underflow");
96.           return q[first];
97.      }
99.      /**
100.       * Returns an iterator that iterates over the items in this queue in FIFO
101.       * order.
102.       * 
103.       * @return an iterator that iterates over the items in this queue in FIFO
104.       *         order
105.       */
106.      public Iterator<Item> iterator() {
107.           return new ArrayIterator();
108.      }
110.      // an iterator, doesn't implement remove() since it's optional
111.      private class ArrayIterator implements Iterator<Item> {
112.           private int i = 0;
114.           public boolean hasNext() {
115.                return i < N;
116.           }
118.           public void remove() {
119.                throw new UnsupportedOperationException();
120.           }
122.           public Item next() {
123.                if (!hasNext())
124.                     throw new NoSuchElementException();
125.                Item item = q[(i + first) % q.length];
126.                i++;
127.                return item;
128.           }
129.      }
130.      
131.      public static void main(String[] args) {
132.           ResizingArrayQueue<String>s=new ResizingArrayQueue<String>();
133.           s.enqueue("ppppp");
134.           s.enqueue("eeee");
135.           System.out.println(s.dequeue());
136.      }
137. }

 

栈：

下压栈 ，后进先出，好比浏览网页，的后退键等。

java实现：

链表：

1. import java.util.Iterator;
2. import java.util.NoSuchElementException;
3. import java.util.Stack;
5. public class LinkedStack<Item> implements Iterable<Item> {
6.      private int N;
7.      private Node first;
9.      private class Node {
10.           private Item item;
11.           private Node next;
12.      }
14.      public LinkedStack() {
15.           first = null;
16.           N = 0;
17.           assert check();
18.      }
20.      public boolean isEmpty() {
21.           return first == null;
22.      }
24.      public int size() {
25.           return N;
26.      }
28.      public void push(Item item) {
29.           Node oldfirst = first;
30.           first = new Node();
31.           first.next = oldfirst;
32.           first.item = item;
33.           N++;
34.           assert check();
35.      }
37.      public Item pop() {
38.           if (isEmpty()) {
39.                throw new NoSuchElementException("Stack underflow");
40.           }
41.           Item item = first.item;
42.           first = first.next;
43.           N--;
44.           assert check();
45.           return item;
46.      }
48.      public Item peak() {
49.           if (isEmpty())
50.                throw new NoSuchElementException("Queue underflow");
51.           return first.item;
52.      }
54.      public String toString() {
55.           StringBuilder s = new StringBuilder();
56. //          for (Item item : this)
57. //               s.append(item + " ");
58.           for (Node x =first; x!=null; x=x.next) {
59.                s.append(x.item + " ");
60.           }
61.           return s.toString();
62.      }
64.      private boolean check() {
65.           if (N==0) {
66.                if (first==null) {
67.                     return false;
68.                }else if (N==1) {
69.                     if (first==null) {
70.                          return false;
71.                     }
72.                     if (first.next!=null) {
73.                          return false;
74.                     }
75.                }else {
76.                     if (first.next==null) {
77.                          return false;
78.                     }
79.                }
80.           }
81.           int numberOfNodes = 0;
82.         for (Node x = first; x != null; x = x.next) {
83.             numberOfNodes++;
84.         }
85.         if (numberOfNodes != N) return false;
87.         return true;
88.      }
90.      @Override
91.      public Iterator<Item> iterator() {
92.           // TODO Auto-generated method stub
93.           return new ListIterator();
94.      }
96.      private class ListIterator implements Iterator<Item> {
97.           private Node current = first;
99.           public boolean hasNext() {
100.                return current != null;
101.           }
103.           public void remove() {
104.                throw new UnsupportedOperationException();
105.           }
107.           public Item next() {
108.                if (!hasNext())
109.                     throw new NoSuchElementException();
110.                Item item = current.item;
111.                current = current.next;
112.                return item;
113.           }
114.      }
115.      
116.      public static void main(String[] args) {
117.           LinkedStack<String>s=new LinkedStack<String>();
118.           Stack<Character>a=new Stack<Character>();
119.           a.peek();
120.      }
122. }

数组实现：

1. 1. import java.util.Iterator;
   2. import java.util.NoSuchElementException;
   4. public class ResizingArrayStack<Item> implements Iterable<Item> {
   5.      private Item[] a;
   6.      private int N;
   8.      public ResizingArrayStack() {
   9.           a = (Item[]) new Object[2];
   10.      }
   12.      public boolean isEmpty() {
   13.           return N == 0;
   14.      }
   16.      public int size() {
   17.           return N;
   18.      }
   20.      private void resize(int cap) {
   21.           assert cap >= N;
   22.           Item[] temp = (Item[]) new Object[cap];
   23.           for (int i = 0; i < N; i++) {
   24.                temp[i] = a[i];
   25.           }
   26.           a = temp;
   27.      }
   29.      public void push(Item item) {
   30.           if (N == a.length) {
   31.                resize(2 * a.length);
   32.           }
   33.           a[N++] = item;
   34.      }
   36.      public Item pop() {
   37.           if (isEmpty()) {
   38.                throw new NoSuchElementException("Stack underflow");
   39.           }
   40.           Item item = a[N - 1];
   41.           a[N - 1] = null;
   42.           N--;
   43.           if (N > 0 && N == a.length / 4) {
   44.                resize(a.length / 2);
   45.           }
   46.           return item;
   47.      }
   49.      public Item peek() {
   50.           if (isEmpty())
   51.                throw new NoSuchElementException("Stack underflow");
   52.           return a[N - 1];
   53.      }
   55.      @Override
   56.      public Iterator<Item> iterator() {
   57.           return new ReverseArrayIterator();
   58.      }
   60.      private class ReverseArrayIterator implements Iterator<Item> {
   61.           private int i;
   63.           public ReverseArrayIterator() {
   64.                i = N - 1;
   65.           }
   67.           public boolean hasNext() {
   68.                return i >= 0;
   69.           }
   71.           public void remove() {
   73.                throw new UnsupportedOperationException();
   74.           }
   76.           public Item next() {
   77.                if (!hasNext())
   78.                     throw new NoSuchElementException();
   79.                return a[i--];
   80.           }
   81.      }
   83.      public static void main(String[] args) {
   84.           ResizingArrayStack<String> s = new ResizingArrayStack<String>();
   85.           s.push("kk");
   86.           s.push("pp");
   87.           s.push("pp");
   88.           s.push("pp");
   89.           System.out.println(s.pop());
   90.           System.out.println(s.pop());
   91.           System.out.println(s.pop());
   92.           System.out.println(s.pop());
   93.           System.out.println(s.N);
   94.      }
   95. }