首页 > 系统服务 > 详细

algorithms第四版学习进程（一）背包，栈，队列

时间：2015-06-22 16:13:04      阅读：252      评论：0      收藏：0      [点我收藏+]

背包：

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

主要的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. 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. }

algorithms第四版学习进程（一）背包，栈，队列

原文：http://www.cnblogs.com/wuwulalala/p/4593317.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！