目录
第1关：实现基于数组的
任务描述
相关知识
栈
栈的数组表示
Java 泛型简介
泛型方法
泛型类应用场景示例
代码：
第2关：实现基于链表的栈
任务描述
相关知识
栈的链式存储
入栈
出栈
代码：
第3关：基于数组的队列
任务描述
相关知识
队列
队列的数组实现
循环队列
代码：
第4关：基于链表的队列
任务描述
相关知识
链式队列
入队操作
代码：
第1关：实现基于数组的
任务描述
在日常生活中，栈是常见的事物。餐厅里的一叠盘子、弹夹都是栈的例子。如弹夹，最先弹出的子弹是最后压入的那颗。
栈可以用数组实现，也可以用链表实现。
本关任务：基于数组，利用Java中泛型实现一个栈，并具有基本的入栈、出栈功能。
相关知识
栈
栈，是一种运算受限的线性表；仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。对栈的基本操作有push(入栈)和pop(出栈)，前者是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；后者是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
一个栈的示意图：
下面是1 2 3入栈出栈的示意图：
用数组表示线性表的相关知识可以参考之前的实训。
栈的数组表示
我们可以用一个数组S[1...n]来实现一个最多容纳n个元素的栈。该数组有一个top属性，指向最新插入的元素。栈中包含的元素为S[1...top]，其中S[1]是栈底元素，S[top]是栈顶元素。
下图是栈的数组实现的一个实例，top指向的是栈顶元素的下标：
(a)栈S内有4个元素。栈顶元素为9； (b)调用push(17)和push(3)后的栈S； (c)调用pop()并返回栈顶元素3的栈S。虽然3仍然在数组里，但它已经不在栈内了，此时栈顶的元素是17。
Java 泛型简介
Java 泛型是JDK 5中引入的一个新特性， 泛型提供了编译时类型安全检测机制，该机制允许程序员在编译时检测到非法的类型。 泛型的本质是参数化类型，也就是说所操作的数据类型被指定为一个参数。
泛型方法
假定我们有这样一个需求：写一个排序方法，能够对整型数组、字符串数组甚至其他任何类型的数组进行排序，该如何实现？答案是使用Java泛型。 使用Java泛型的概念，我们可以写一个泛型方法来对一个对象数组排序。然后，调用该泛型方法来对整型数组、浮点数数组、字符串数组等进行排序。
下面是定义泛型方法的规则：
- 所有泛型方法声明都有一个类型参数声明部分（由尖括号分隔），该类型参数声明部分在方法返回类型之前（在下面例子中的
）； - 每一个类型参数声明部分包含一个或多个类型参数，参数间用逗号隔开。一个泛型参数，也被称为一个类型变量，是用于指定一个泛型类型名称的标识符；
- 类型参数能被用来声明返回值类型，并且能作为泛型方法得到的实际参数类型的占位符；
- 泛型方法体的声明和其他方法一样。注意类型参数只能代表引用型类型，不能是原始类型（如int,double,char的等）。
泛型方法实例：
public class GenericMethodTest { // 泛型方法 printArray public static < E > void printArray( E[] inputArray ) { // 输出数组元素 for ( E element : inputArray ){ System.out.printf( "%s ", element ); } System.out.println(); } public static void main( String args[] ) { // 创建不同类型数组： Integer, Double 和 Cha\fracter Integer[] intArray = { 1, 2, 3, 4, 5 }; Double[] doubleArray = { 1.1, 2.2, 3.3, 4.4 }; Cha\fracter[] charArray = { 'H', 'E', 'L', 'L', 'O' }; System.out.println( "整型数组元素为:" ); printArray( intArray ); // 传递一个整型数组 System.out.println( "\n双精度型数组元素为:" ); printArray( doubleArray ); // 传递一个双精度型数组 System.out.println( "\n字符型数组元素为:" ); printArray( charArray ); // 传递一个字符型数组 } }泛型类应用场景示例
假设要对一个盒子编程，我们需要定义一个Box类，具体定义如下：
public class Box { private String obj; public void set(String obj) { this.obj = obj; } public String get() { return obj; } }这是最常见的做法，这样做的一个坏处是Box中的obj只能是String类型，如果我们今后需要把obj改为Integer等其他类型的元素，还必须要另外重写一个Box，代码得不到复用，使用泛型可以很好的解决这个问题。
public class Box{ // T stands for "Type" private T obj; public void set(T obj) { this.obj = obj; } public T get() { return obj; } } 这样我们的Box类便可以得到复用，我们可以将T替换成任何我们想要的类型：
BoxintegerBox = new Box (); Box doubleBox = new Box (); Box stringBox = new Box ();
代码：
package step1; import java.util.NoSuchElementException; /** * Created by sykus on 2018/1/26. */ public class MyStack{ private T[] S; private int top;//栈顶元素下标，初始为-1 public MyStack() { this(1); } public MyStack(int capacity) { S = (T[]) new Object[capacity]; top = -1; } /** * 入栈操作，把item压入栈中 * * @param item */ public void push(T item) { int len = S.length; if (top == len - 1) { resize(2 * len); } /********** Begin *********/ S[++top]=item;//top栈顶由-1开始，先自增，再储存元素 /********** End *********/ } /** * 返回栈顶元素并从栈中移除 * * @return */ public T pop() { if (isEmpty()) { throw new NoSuchElementException("栈为空！"); } /********** Begin *********/ return S[top--];//直接返回top位置的元素，并减，因为栈是先进后出 /********** End *********/ } /** * 判断栈是否为空 * * @return */ public boolean isEmpty() { if (top < 0) return true; else return false; } /** * 动态扩展数组大小 * * @param capacity */ private void resize(int capacity) { assert capacity > top; T[] tmp = (T[]) new Object[capacity]; for (int i = 0; i <= top; i++) { tmp[i] = S[i]; } S = tmp; } }
预期输入：
- to be or not to - be - - that - - - is
预期输出：
- to be not that or be
第2关：实现基于链表的栈
任务描述
上一关，我们介绍了Java泛型，并用数组实现了栈，这一关我们将基于链表实现栈。
本关任务：基于单链表实现一个栈，并具备入栈、出栈功能。
相关知识
栈的链式存储
栈的链式存储结构称为链栈，是运算受限的单链表，其插入和删除操作只能在表头进行，如下图：
入栈
基于单链表实现的栈，入栈就是插入一个新结点，这里在头结点后插入新结点：
上图中，首先让新结点的next指向原来的栈顶元素head.next，保持对整个链表的引用，再把head.next指向新结点。
出栈
同样，出栈就是删除第一个结点：
删除头结点，可以直接把head.next指向head.next.next。
此外，这里同样用了泛型，相关Java泛型知识请参考上一关。
代码：
package step2; import java.util.NoSuchElementException; /** * Created by sykus on 2017/12/29. */ public class MyStack{ private Node head;//头结点 private Node top;//栈顶 private int size;//栈中元素个数 public MyStack() { head = new Node (); head.next = null; top = null;//栈顶初始化为null size = 0; } /** * 把item压入栈中 * * @param item */ public void push(E item) { /********** Begin *********/ Node newNode=new Node();//创建一个新的结点 newNode.item=item;//将值存入新结点 newNode.next=head.next;//确定新结点指向（头的当前结点） head.next=newNode;//将头的指向改为新结点 top=newNode;//栈顶指向新结点 ++size;//元素个数+1 /********** End *********/ } /** * 返回它栈顶元素并删除 */ public E pop() { if (isEmpty()) throw new NoSuchElementException("栈为空！"); /********** Begin *********/ Node t=top;//保存删除元素，这里我把 删了运行不了 top=top.next;//栈顶指向栈的下一个元素，因为栈顶需要被删除 head.next=top;//头指向栈顶，此时栈顶已经改为下一个元素 --size;//元素个数-1 return t.item;//返回删除元素 /********** End *********/ } /** * 返回栈中元素个数 * * @return */ public int size() { return size; } /** * 判断一个栈是否为空 * * @return */ public boolean isEmpty() { return (null == head); } //链表结点内部类 private static class Node { private E item; private Node next; } }
以下是测试样例： 测试输入：to be or not to - be - - that - - - is 预期输出：to be not that or be
第3关：基于数组的队列
任务描述
像栈一样，队列也是表。但使用队列时，插入在一端进行而删除则在另一端进行。
如同栈的情形一样，任何的表的实现对于队列来说都是合法的。
本关任务：基于数组实现一个循环队列，并具有基本的添加、删除功能。
相关知识
队列
队列实现的是一种先进先出的策略，队列上的插入操作称为入队(enqueue)，删除操作称为出队(dequeue)。队列的先进先出特性类似于收银台前排队等待结账的一排顾客。队列有队头(head)和队尾(tail)，当有新元素入队时，它被放到队尾的位置，就像一个新到来的顾客排在队伍末端一样。而出队的元素则总是在队头的那个，就像排在队伍前面等待最久的那个顾客一样。下图是一个队列的抽象模型：
队列的数组实现
对于一个队列数据结构，我们使用一个数组Q，以及队头head和队尾tail的位置来表示。head和tail代表队列的两端。下图表明利用数组Q[0...n]来实现一个最多容纳n+1个元素的队列的一种方式。该队列有一个属性Q.head指向队头元素。而属性Q.tail则指向下一个新元素将要插入的位置。队列中的元素存放在位置Q.head，Q.head+1，……，Q.tail-1。初始时有Q.head=Q.tail=0。
入队出队的操作应该是很清楚的。为使一个元素x入队，即执行enqueue(x)，让Q[tail]=x，然后使tail增1。若使元素出队（dequeue），我们返回Q[head]处的值，且使head增1。
循环队列
上述这种实现存在一个问题。以上图为例，经过12次入队操作后队列似乎满了，因为此时tail已经超过数组尾端了，再次执行入队操作会造成数组越界。然而，队列中也许只剩下几个元素。因为可能有若干元素出队了。像栈一样，即使有许多操作的情况下，队列也常常不是很大。 一个简单的解决方法是，只要head或tail到达数组尾端，它就绕回开头。我们称这种队列称为循环队列。
下图是一个队列实例。
这里我们利用数组Q[0...12]实现一个循环队列。
- (a)队列包含5个元素，位于Q[6...10]；
- (b)依次调用Q.enqueue(17)，Q.enqueue(3)，Q.enqueue(5)后的队列；
- (c)调用Q.dequeue()方法并返回原队头值15后，队列的构成。此时新的队头是元素6。
代码：
package step3; /** * Created by zengpeng on 2018/1/30. */ public class MyQueue{ private T[] Q; private int head; private int tail; private int size; public MyQueue() { this(1); } public MyQueue(int capacity) { Q = (T[]) new Object[capacity]; size = 0; head = tail = 0; } /** * 入队操作 * * @param item */ public void enqueue(T item) { /********** Begin *********/ Q[tail]=item;//当前下标添加一个数 tail=(tail+1)%Q.length;//tail从-1开始，到顶后可能再到头所以要取余 size++;//元素个数+1 /********** End *********/ } /** * 出队操作 * * @return */ public T dequeue() { /********** Begin *********/ T s=Q[head];//保存要删除元素 head=(head+1)%Q.length;//同理 size--;//元素-1 return s;//返回删除元素 /********** End *********/ } /** * 判断队列是否为空 * @return */ public boolean isEmpty() { return (head == tail) && (size < Q.length); } public int size() { return size; } }
以下是测试样例：
测试输入：to be or not to - be - - that - - - is 预期输出：
- to
- be
- or
- not
- to
- be
第4关：基于链表的队列
任务描述
在上一关，我们用数组实现了队列，但是在使用时需要预先估计所需队列的大小。而链式队列具有内存动态分配，内存利用率高的特点，在一些无法预先估计所需队列大小的场合使用链式队列是一个十分好的选择。
本关任务：实现链式队列，并具备入队、出队操作。
相关知识
链式队列
队列的链式存储结构简称为链式队列。它实际上是一个限制仅在表头删除和表尾插入的单链表。 链式队列的存储结构如下图所示：
其中`front`指向队头，`tail`指向队尾。出队操作在队头进行，入队操作在队尾进行。 ##### 出队操作入队操作
代码：
package step4; import java.util.NoSuchElementException; /** * Created by sykus on 2017/12/29. */ public class MyQueue{ private Node head;// 头结点，不存数据 private Node front;//指向队头结点 private Node tail;//指向队尾结点 private int size; public MyQueue() { head = new Node (); front = tail = null; size = 0; } /** * 入队 * * @param item */ public void enqueue(T item) { /********** Begin *********/ Node oldTail=tail;//保存旧的队尾 Node newNode=new Node();//创建新结点 newNode.item=item;//给新结点添加元素 if(front==null)//如果为空队列 { head.next=newNode;//头指向新结点 front=newNode;//队头为新结点 } else//不为 { oldTail.next=newNode;//老队尾指向新结点 } tail=newNode;//令新结点为队尾 size++;//元素个数+1 /********** End *********/ } /** * 出队 * * @return */ public T dequeue() { if (isEmpty()) throw new NoSuchElementException("队列为空！"); /********** Begin *********/ T s=front.item;//保存当前元素 head.next=front.next;//头指向改为队头的下一个 front=head.next;//队头改为头的下一个（此时已经为队头的下一个） size--;//元素-1 return s;//返回删除元素 /********** End *********/ } /** * 返回队列中元素数量 * * @return */ public int size() { return size; } /** * 判断一个队列是否为空 * * @return */ public boolean isEmpty() { return (front == null); } /** * 链表结点内部类 */ private static class Node { private E item; private Node next; } }
以下是测试样例：
测试输入：to - be or not to - be - - that - - is 预期输出：
- to be or not to be
- 2