背包、队列和栈实战

系统管理员 2021-07-24 12:29 373阅读 0赞

**一 背包相关API**

<table style="width:621px;"> 
 <tbody> 
  <tr> 
   <td colspan="2"> <p style="text-indent:0;">背包</p> </td> 
  </tr> 
  <tr> 
   <td colspan="2"> 
    <div>
      public class Bag&lt;Item&gt; implements Iterable&lt;Item&gt; 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Bag() 
    </div> </td> 
   <td> 
    <div>
      创建一个空的背包 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      public void add(Item item) 
    </div> </td> 
   <td> 
    <div>
      添加一个元素 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      public boolean isEmpty() 
    </div> </td> 
   <td> 
    <div>
      背包是否为空 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      public int size() 
    </div> </td> 
   <td> 
    <div>
      背包中元素数量 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

**二 队列相关API**

<table style="width:625px;"> 
 <tbody> 
  <tr> 
   <td colspan="2"> 
    <div>
      先进先出队列 
    </div> </td> 
  </tr> 
  <tr> 
   <td colspan="2"> 
    <div>
      public class Queue&lt;Item&gt; implements Iterable&lt;Item&gt; 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      public Queue() 
    </div> </td> 
   <td> 
    <div>
      创建空队列 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      public void enqueue(Item item) 
    </div> </td> 
   <td> 
    <div>
      添加一个元素 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      public Item dequeue() 
    </div> </td> 
   <td> 
    <div>
      删除最早添加的元素 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      public boolean isEmpty() 
    </div> </td> 
   <td> 
    <div>
      队列是否为空 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      public int size() 
    </div> </td> 
   <td> 
    <div>
      队列中的元素数量 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

**三 栈相关API**

<table style="width:623px;"> 
 <tbody> 
  <tr> 
   <td colspan="2"> 
    <div>
      下压栈 
    </div> </td> 
  </tr> 
  <tr> 
   <td colspan="2"> 
    <div>
      public class Stack&lt;Item&gt; implements Iterable&lt;Item&gt; 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      public Stack() 
    </div> </td> 
   <td> 
    <div>
      创建一个空栈 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      public void push(Item item) 
    </div> </td> 
   <td> 
    <div>
      添加一个元素 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      public Item pop() 
    </div> </td> 
   <td> 
    <div>
      删除最近添加的元素 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      public boolean isEmpty() 
    </div> </td> 
   <td> 
    <div>
      栈是否为空 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      public int size() 
    </div> </td> 
   <td> 
    <div>
      栈中元素数量 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

**四 自动装箱和拆箱**

1 代码

Stack<Integer> stack = new Stack<Integer>();
    stack.push(i);            // 自动装箱（int > Integer）
    int i = stack.pop();      // 自动拆箱（Interger->int）

2 定义

自动将一个原始数据类型转换为一个封装类型被称为自动装箱，自动将一个封装类型转换为一个原始数据类型被称为自动拆箱。

**五 可迭代的集合类型**

Queue<Item> collection = new Queue<Item>();

如果集合是可迭代的，可用下面一行打印出来。

for(item t : collection){
        StdOut.println(t);
    }

**六 背包**

1 定义

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

使用Bag可以说明元素的处理顺序不重要。

2 任务

计算标准输入中的所有double值的平均值和样本标准差。

3 代码

package MyBag;
    
    import common.Bag;
    import common.StdIn;
    import common.StdOut;
    
    /**
    * Copyright (C), 2020-2020, XXX有限公司
    * FileName: Mystack
    * Author:   cakin
    * Date:     2020/1/17
    * Description: 计算平均值为标准差
    */
    public class MyBag {
        public static void main( String[] args ) {
            Bag<Double> numbers = new Bag<Double>();
            while (!StdIn.isEmpty())
                numbers.add(StdIn.readDouble());
            int N = numbers.size();
            double sum =0.0;
            for (double x : numbers) {
                sum+=x;
            }
            double mean = sum / N;
            sum = 0.0;
            for(double x : numbers)
                sum +=(x-mean)*(x-mean);
            double std = Math.sqrt(sum/(N-1));
    
    
            StdOut.printf("Mean: %.2f\n",mean);
            StdOut.printf("Std dev: %.2f\n",std);
        }
    }

4 测试结果

100
    100
    100
    100
    100
    ^D
    Mean: 100.00
    Std dev: 0.00

**七 队列**

1 测试代码

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)");
    }

2 测试结果

a b c d e f -
    a -
    b ^D
    (4 left on queue)

**八 堆栈**

1 任务

输入的数字倒序

2 代码

package MyStack;
    
    import common.Stack;
    import common.StdIn;
    import common.StdOut;
    
    /**
    * Copyright (C), 2020-2020, XXX有限公司
    * FileName: Reverse
    * Author:   cakin
    * Date:     2020/1/17
    * Description: 整数倒序
    */
    public class Reverse {
        public static void main( String[] args ) {
            Stack<Integer> stack = new Stack<Integer>();
            while(!StdIn.isEmpty()){
                stack.push(StdIn.readInt());
            }
    
    
            for(int i : stack){
                StdOut.println(i);
            }
        }
    }

3 测试用例

1 2 3 4 5 6
    ^D
    6
    5
    4
    3
    2
    1

九 参考代码

[https://gitee.com/cakin24/Algorithm][https_gitee.com_cakin24_Algorithm]

[https_gitee.com_cakin24_Algorithm]: https://gitee.com/cakin24/Algorithm