前言

使用的是《算法》第四版英文版，主要是习题解答。

书中jar包的导入请戳：算法（第四版）中algs4.jar下载和使用

EXERCISES

1.3.1

public class FixedCapacityStackOfStrings {private String[] a;     // stack entriesprivate int N;          // sizepublic FixedCapacityStackOfStrings(int cap) {a = new String[cap];}public boolean isEmpty() {return N == 0;}public int size() {return N;}public void push(String item) {a[N++] = item;}public String pop() {return a[--N];}// 添加的方法public boolean isFull() {return N == a.length;}
}

1.3.2

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;import java.util.Iterator;public class Stack<T> implements Iterable<T> {private Node first;     // top of stack (most recently added node)private int N;          // number of itemsprivate class Node {T item;Node next;}public boolean isEmpty() {return first == null;}public int size() {return N;}public void push(T item) {Node oldFirst = first;first = new Node();first.item = item;first.next = oldFirst;N++;}public T pop() {T item = first.item;first = first.next;N--;return item;}@Overridepublic Iterator<T> iterator() {return new ListIterator();}private class ListIterator implements Iterator<T> {private Node current = first;public boolean hasNext() {return current != null;}public void remove() { }public T next() {T item = current.item;current = current.next;return item;}}public static void main(String[] args) {Stack<String> s = new Stack<String>();while (!StdIn.isEmpty()) {String item = StdIn.readString();if (!item.equals("-"))s.push(item);else if (!s.isEmpty())StdOut.print(s.pop() + " ");}StdOut.println("(" + s.size() + " left on stack)");}
}

1.3.3

b、f、g

1.3.4

import java.util.Scanner;public class Parentheses {public static void main(String[] args) {Scanner in = new Scanner(System.in);String s = in.nextLine();Stack<Character> sk = new Stack<>();boolean res = true;for (int i = 0; i < s.length() && res; i++) {// 左括号入栈if (s.charAt(i) == '{' || s.charAt(i) == '[' || s.charAt(i) == '(')sk.push(s.charAt(i));if (!sk.isEmpty()) {if (s.charAt(i) == '}' && sk.pop() != '{')res = false;if (s.charAt(i) == ']' && sk.pop() != '[')res = false;if (s.charAt(i) == ')' && sk.pop() != '(')res = false;}if (sk.isEmpty() && (s.charAt(i) == ')' || s.charAt(i) == ']' || s.charAt(i) == '}'))res = false;}System.out.println(res);}
}

1.3.5

1.3.6

将队列中的元素进行逆序

1.3.7

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;import java.util.Iterator;public class Stack<T> implements Iterable<T> {.........			// 省略部分同1.3.2public T peek() {return first.item;}
}

1.3.8

import edu.princeton.cs.algs4.StdIn;import java.util.Iterator;public class DoublingStackOfStrings<T> implements Iterable<T> {private T[] a = (T[]) new Object[1];private int n;public int size() {return n;}public boolean isEmpty() {return n == 0;}public void push(T item) {if (n == a.length)resize(2 * n);a[n++] = item;}public T pop() {T item = a[--n];a[n] = null;if (n > 0 && n == a.length / 4)resize(2 * n);return item;}public int arraySize() {return a.length;}public void resize(int max) {T[] items = (T[]) new Object[max];for (int i = 0; i < n; i++) {items[i] = a[i];}a = items;}@Overridepublic Iterator<T> iterator() {return new ArrayIterator();}private class ArrayIterator implements Iterator<T> {private int i = n - 1;@Overridepublic boolean hasNext() {return i >= 0;}@Overridepublic T next() {return a[i--];}}public static void main(String[] args) {DoublingStackOfStrings<String> sk = new DoublingStackOfStrings<>();String[] inputs = StdIn.readAllStrings();for (int i = 0; i < inputs.length; i++) {if (inputs[i].equals("-"))sk.pop();elsesk.push(inputs[i]);}for (String s : sk)System.out.println(s + " ");System.out.println("ArraySize: " + sk.arraySize());}
}

1.3.9

import java.util.Scanner;// 我个人理解应该就是每遇到一个右括号，就取数字栈栈顶两个数字和符号栈一个运算符号
public class Solution {public static void main(String[] args) {Scanner in = new Scanner(System.in);String str = in.nextLine();String[] inputs = str.split(" ");Stack<String> sk1 = new Stack<>();       // 存储数字Stack<String> sk2 = new Stack<>();       // 存储运算符号for (String s : inputs) {if (isOperator(s))sk2.push(s);else if (s.equals(")")) {String num1 = sk1.pop();String num2 = sk1.pop();String op = sk2.pop();sk1.push("(" + num2 + " " + op + " " + num1 + ")");} elsesk1.push(s);}System.out.println(sk1.pop());}private static boolean isOperator(String s) {return (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/"));}
}

1.3.10

import java.util.Scanner;
import java.util.Stack;public class Solution {public static void main(String[] args) {Scanner in = new Scanner(System.in);String str = in.nextLine();System.out.println(InfixToPostfix(str));}public static String InfixToPostfix(String str) {String[] inputs = str.split(" ");Stack<String> sk = new Stack<>();StringBuilder res = new StringBuilder();for (String s : inputs) {if (isOperator(s))sk.push(s);else if (s.equals("("))continue;else if (s.equals(")"))res.append(sk.pop());elseres.append(s);}return res.toString();}private static boolean isOperator(String s) {return (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/"));}
}

1.3.11

import java.util.Scanner;
import java.util.Stack;public class EvaluatePostfix {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 输入的后缀表达式每个字符用空格隔开String str = in.nextLine();Stack<String> sk = new Stack<>();String[] inputs = str.split(" ");for (String s : inputs) {// 遇到运算符，从栈中弹出两个数字进行运算if (isOperator(s)) {int num1 = Integer.parseInt(sk.pop());int num2 = Integer.parseInt(sk.pop());if (s.equals("+"))sk.push(Integer.toString(num1 + num2));if (s.equals("-"))sk.push(Integer.toString(num1 - num2));if (s.equals("*"))sk.push(Integer.toString(num1 * num2));if (s.equals("/")) {if (num2 == 0)throw new ArithmeticException("divide by zero");elsesk.push(Integer.toString(num1 / num2));}} elsesk.push(s);}System.out.println(sk.pop());}private static boolean isOperator(String s) {return (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/"));}
}

1.3.12

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;import java.util.Iterator;public class Stack<T> implements Iterable<T> {...			// 省略部分同1.3.7......public static <T> Stack<T> copy(Stack<T> sk) {Iterator<T> it = sk.iterator();Stack<T> res = new Stack<>();Stack<T> temp = new Stack<>(); while (it.hasNext())temp.push(it.next());it = temp.iterator();while (it.hasNext())res.push(it.next());return res;}
}

1.3.13

b、c、d

1.3.14

public class ResizingArrayOfStrings {private int first;private int last;private int size;private String[] data;public ResizingArrayOfStrings() {first = 0;last = 0;size = 1;data = new String[size];}public boolean isEmpty() {return first == last;}public int getSize() {return last - first;}public void enqueue(String s) {if (last == size)resizing(2 * getSize());data[last++] = s;}public String dequeue() {if (getSize() < size / 4)resizing(2 * getSize());return data[first++];}private void resizing(int n) {String[] temp = new String[n];int index = 0;for (int i = first; i < last; i++)temp[index++] = data[i];data = temp;size = n;last = last - first;first = 0;}
}

1.3.15

import java.util.Iterator;
import java.util.Scanner;public class MyQueue<T> implements Iterable<T> {private Node first;private Node last;private int n;private class Node {T item;Node next;}public boolean isEmpty() {return n == 0;}public int size() {return n;}public void enqueue(T item) {Node oldLast = last;last = new Node();last.item = item;last.next = null;if (isEmpty())first = last;elseoldLast.next = last;n++;}public T dequeue() {T res = first.item;first = first.next;if (isEmpty())last = null;n--;return res;}@Overridepublic Iterator<T> iterator() {return new QueueIterator();}private class QueueIterator implements Iterator<T> {private Node cur = first;@Overridepublic boolean hasNext() {return cur != null;}@Overridepublic T next() {T res = cur.item;cur = cur.next;return res;}}// 将所有输入的字符串入队，队列大小为n// 然后将n - k个字符串出队，最后队列的出队字符串即为倒数第K个字符串public static void main(String[] args) {Scanner in = new Scanner(System.in);int k = in.nextInt();MyQueue<String> myQueue = new MyQueue<>();while (in.hasNext()) myQueue.enqueue(in.next());int size = myQueue.size();for (int i = 0; i < size - k; i++) {myQueue.dequeue();}System.out.println(myQueue.dequeue());}
}

1.3.16

public class Date {private int year;private int month;private int day;public Date(int year, int month, int day) {this.year = year;this.month = month;this.day = day;}public Date(String date) {String[] inputs = date.split("/");if (inputs.length != 3)throw new IllegalArgumentException("Arguments illegal!");month = Integer.parseInt(inputs[0]);day = Integer.parseInt(inputs[1]);year = Integer.parseInt(inputs[2]);}public int getYear() {return year;}public int getMonth() {return month;}public int getDay() {return day;}@Overridepublic String toString() {return getMonth() + "/" + getDay() + "/" + getYear();}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null) return false;if (this.getClass() != o.getClass()) return false;Date that = (Date) o;if (this.day != that.day) return false;if (this.month != that.month) return false;if (this.year != that.year) return false;return true;}public static Date[] readDates(String date) {String[] inputs = date.split(" ");int length = inputs.length;MyQueue<Date> myQueue = new MyQueue<>();for (int i = 0; i < length; i++) {myQueue.enqueue(new Date(inputs[i]));}Date[] res = new Date[length];for (int i = 0; i < length; i++) {res[i] = myQueue.dequeue();}return res;}
}

1.3.17

class Transaction implements Comparable<Transaction> {private String name;private Date date;private double amount;private String transaction;public Transaction(String name, Date date, double amount) {this.name = name;this.date = date;this.amount = amount;}public Transaction(String transaction) {this.transaction = transaction;}public String getName() {return name;}public Date getDate() {return date;}public double getAmount() {return amount;}@Overridepublic String toString() {return "Transaction{" + getName() + " " + getDate() + " " + getAmount() + "}";}@Overridepublic int compareTo(Transaction o) {if (this.amount > o.amount)return 1;else if (this.amount < o.amount)return -1;elsereturn 0;}
}

LINKED-LIST EXERCISES

1.3.18

略

1.3.19

public class LinkedList<T> {private Node first;private int size;private class Node {T item;Node next;}public void deleteLastNode() {Node cur = first;if (cur == null)return;Node curNext = cur.next;if (curNext == null)first = null;while (curNext.next != null) {cur = curNext;curNext = curNext.next;}cur.next = null;}
}

1.3.20

public class LinkedList<T> {private Node first;private int size;private class Node {T item;Node next;}public void delete(int k) {if (k <= 0 || first == null)return;if (k == 1) {first = first.next;return;}k--;Node cur = first;// 查找到第K-1个元素while (cur != null && --k != 0)cur = cur.next;// 整个链表长度小于kif (k != 0 || cur == null || cur.next == null)return;else    // 正常删除cur.next = cur.next.next;}
}

1.3.21

import java.util.LinkedList;public class Solution {public static <T> boolean find(LinkedList<T> first, String key) {for (T item : first) {if (item.equals(key))return true;}return false;}
}

1.3.22

略

1.3.23

略

1.3.24

public class MyLinkedList<T> {private Node<T> first;private int size;private class Node<T> {T item;Node<T> next;}public void removeAfter(Node<T> node) {if (node == null || node.next == null)return;Node<T> cur = node.next;node.next = null;while (cur != null) {Node<T> temp = cur.next;cur.next = null;cur = temp;}}
}

1.3.25

public class MyLinkedList<T> {private Node<T> first;private int size;private class Node<T> {T item;Node<T> next;}public void insertAfter(Node<T> list1, Node<T> list2) {if (list1 == null || list2 == null)return;list2.next = list1.next;list1.next = list2;}
}

1.3.26

public class MyLinkedList<T> {private Node first;private int size;private class Node {T item;Node next;}public void remove(Node node, String key) {while (node != null && key.equals(node.item))node = node.next;Node cur = node;while (cur != null && cur.next != null) {Node curNext = cur.next;if (key.equals(curNext.item))cur.next = curNext.next;elsecur = curNext;}}
}

1.3.27

public class MyLinkedList {private Node first;private int size;private class Node {int item;Node next;}public int max(Node node) {int res = 0;while (node != null) {if (node.item > res)res = node.item;node = node.next;}return res;}
}

1.3.28

public class MyLinkedList<T> {private Node<T> first;private int size;private static class Node<T> {T item;Node<T> next;//	构造函数Node(T item, Node<T> next) {this.item = item;this.next = next;}}public int max(Node<Integer> node) {if (node.next == null)return node.item;else {int res = max(node.next);return res > node.item ? res : node.item;}}
}

1.3.29

import java.util.Iterator;
import java.util.NoSuchElementException;public class CircularQueue<T> implements Iterable<T> {private Node<T> last;private int size;private static class Node<T> {T item;Node<T> next;}public CircularQueue() {last = null;size = 0;}public boolean isEmpty() {return last == null;}public T dequeue() {if (isEmpty())throw new UnsupportedOperationException("Queue is empty!");T item = last.next.item;if (last.next == last)last = null;elselast.next = last.next.next;return item;}public void enqueue(T item) {Node<T> node = new Node<>();node.item = item;if (last == null) {last = node;node.next = node;} else {node.next = last.next;last.next = node;last = node;}}public int size() {return size;}@Overridepublic Iterator<T> iterator() {return new CircularQueueIterator(last, size());}private class CircularQueueIterator implements Iterator<T> {private Node<T> first;private int size;public CircularQueueIterator(Node<T> first, int size) {if (last == null)this.first = null;elsethis.first = first;this.size = size;}@Overridepublic boolean hasNext() {return size > 0;}@Overridepublic T next() {if (!hasNext())throw new NoSuchElementException();T item = first.item;first = first.next;--size;return item;}}
}

1.3.30

略

1.3.31

答案请戳：算法（Algorithms）第4版 练习 1.3.31

CREATIVE PROBLEMS

1.3.32

import java.util.Iterator;public class Steque<T> implements Iterable<T> {private Node first;private Node last;private int size;private class Node {T item;Node next;}// 头部添加元素public void push(T item) {Node node = new Node();node.item = item;if (isEmpty()) {first = node;last = node;node.next = null;} else {node.next = first;first = node;}++size;}// 头部删除元素public T pop() {if (isEmpty())throw new UnsupportedOperationException("Steque is empty!");T item = first.item;first = first.next;--size;return item;}// 尾部添加元素public void enqueue(T item) {Node node = new Node();node.item = item;node.next = null;if (isEmpty()) {first = node;} else {last.next = node;}last = node;++size;}public boolean isEmpty() {return first == null;}public int size() {return size;}@Overridepublic Iterator<T> iterator() {return new StequeIterator();}private class StequeIterator implements Iterator<T> {private Node cur = first;@Overridepublic boolean hasNext() {return cur != null;}@Overridepublic T next() {T item = cur.item;cur = cur.next;return item;}}public static void main(String[] args) {Steque<String> s = new Steque<>();s.enqueue("a");s.enqueue("b");s.push("c");s.push("d");System.out.println("Steque: ");Iterator<String> it = s.iterator();while (it.hasNext())System.out.println(it.next());System.out.println("pop");while (!s.isEmpty())System.out.println(s.pop());}
}

1.3.33

import java.util.Iterator;public class Deque<T> implements Iterable<T> {private Node head;private Node tail;private int size;private class Node {T item;Node prev;Node next;}public boolean isEmpty() {return size == 0;}public int size() {return size;}public void pushLeft(T item) {Node node = new Node();node.item = item;node.prev = null;if (isEmpty()) {head = tail = node;node.next = null;} else {head.prev = node;node.next = head;head = node;}++size;}public void pushRight(T item) {Node node = new Node();node.item = item;node.next = null;if (isEmpty()) {head = tail = node;node.prev = null;} else {tail.next = node;node.prev = tail;tail = node;}++size;}public T popLeft() {if (isEmpty())throw new UnsupportedOperationException("Deque is empty!");T item = head.item;if (size() == 1)head = tail = null;else {head = head.next;head.prev.next = null;head.prev = null;}--size;return item;}public T popRight() {if (isEmpty())throw new UnsupportedOperationException("Deque is empty!");T item = tail.item;if (size() == 1)head = tail = null;else {tail = tail.prev;tail.next.prev = null;tail.next = null;}--size;return item;}@Overridepublic Iterator<T> iterator() {return new DequeIterator();}private class DequeIterator implements Iterator<T> {private Node cur = head;@Overridepublic boolean hasNext() {return cur != null;}@Overridepublic T next() {T item = cur.item;cur = cur.next;return item;}}
}

1.3.34

import edu.princeton.cs.algs4.StdRandom;import java.util.Iterator;public class RandomBag<T> implements Iterable<T> {private T[] data = (T[]) new Object[1];private int size;public boolean isEmpty() {return size == 0;}public int size() {return size;}public void add(T item) {if (size == data.length)resize(2 * data.length);data[size++] = item;}private void resize(int max) {T[] temp = (T[]) new Object[max];for (int i = 0; i < size; i++) {temp[i] = data[i];}data = temp;}@Overridepublic Iterator<T> iterator() {return new RandomBagIterator();}private class RandomBagIterator implements Iterator<T> {private int[] seq = new int[size];private int index = 0;public RandomBagIterator() {for (int i = 0; i < seq.length; i++) {seq[i] = i;}StdRandom.shuffle(seq);}@Overridepublic boolean hasNext() {return index < size;}@Overridepublic T next() {return data[seq[index++]];}}
}

1.3.35

import edu.princeton.cs.algs4.StdRandom;import java.util.Iterator;public class RandomQueue<T> implements Iterable<T> {private T[] data;private int size;// 这次使用构造函数public RandomQueue() {data = (T[]) new Object[1];size = 0;}public RandomQueue(int capacity) {data = (T[]) new Object[capacity];size = 10;}public int size() {return size;}public boolean isEmpty() {return size == 0;}public void enqueue(T item) {if (size == data.length)resize(2 * data.length);data[size++] = item;}private void resize(int max) {T[] temp = (T[]) new Object[max];for (int i = 0; i < size; i++) {temp[i] = data[i];}data = temp;}public T dequeue() {if (this.isEmpty())throw new UnsupportedOperationException("RandomQueue is empty!");if (size == data.length / 4)resize(data.length / 2);int index = StdRandom.uniform(size);T item = data[index];data[index] = data[--size];data[size] = null;return item;}public T sample() {if (this.isEmpty())throw new UnsupportedOperationException("RandomQueue is empty!");int index = StdRandom.uniform(size);return data[index];}@Overridepublic Iterator<T> iterator() {return new RandomQueueIterator();}private class RandomQueueIterator implements Iterator<T> {private T[] temp;private int index;public RandomQueueIterator() {temp = (T[]) new Object[size];for (int i = 0; i < size; i++) {temp[i] = data[i];}StdRandom.shuffle(temp);index = 0;}@Overridepublic boolean hasNext() {return index < size;}@Overridepublic T next() {return temp[index++];}}public static void main(String[] args) {RandomQueue<Integer> randomQueue = new RandomQueue<>();randomQueue.enqueue(1);randomQueue.enqueue(2);randomQueue.enqueue(3);randomQueue.enqueue(4);randomQueue.enqueue(5);for (int i : randomQueue) {System.out.print(i + " ");}System.out.println();System.out.println(randomQueue.sample());for (int i : randomQueue) {System.out.print(i + " ");}System.out.println();System.out.println(randomQueue.sample());System.out.println(randomQueue.sample());System.out.println(randomQueue.dequeue());for (int i : randomQueue) {System.out.print(i + " ");}}}

1.3.36

代码在1.3.35

1.3.37

import edu.princeton.cs.algs4.StdRandom;import java.util.Scanner;// 找不到自己写的Queue了.....
public class Josephus {public static void main(String[] args) {Scanner in = new Scanner(System.in);int N = in.nextInt();int M = in.nextInt();int[] nums = new int[N];for (int i = 0; i < N; i++) {nums[i] = i;}StdRandom.shuffle(nums);for (int i = 0; i < N; i++) {System.out.print(nums[i] + " ");}System.out.println();boolean[] flag = new boolean[N];    // 标记是否被移除for (int i = 0; i < N; i++) {flag[i] = false;}int count = 1;while (count <= N) {int index = count * M - 1;if (!flag[index % N]) {flag[index % N] = true;count++;}}int res = -1;for (int i = 0; i < N; i++) {if (flag[i])res = nums[i];}System.out.println(res);}}

1.3.38

import java.util.Iterator;public class GeneralizedQueue<T> implements Iterable<T> {private T[] data;private int size;public GeneralizedQueue() {data = (T[]) new Object[1];size = 0;}public boolean isEmpty() {return size == 0;}public int size() {return size;}public void insert(T item) {if (size == data.length)resize(2 * size);data[size++] = item;}private void resize(int max) {T[] temp = (T[]) new Object[max];for (int i = 0; i < size; i++) {temp[i] = data[i];}data = temp;}public T delete(int k) {if (k > size || k <= 0)throw new ArrayIndexOutOfBoundsException("k is bigger than queue size, less than zero or equals zero!");if (size == data.length / 4)resize(data.length / 2);T[] temp = (T[]) new Object[size];T res = data[k - 1];for (int i = 0; i < k - 1; i++) {temp[i] = data[i];}for (int i = k - 1; i < size - 1; i++) {temp[i] = data[i + 1];}data = temp;data[--size] = null;return res;}@Overridepublic Iterator<T> iterator() {return new GeneralizedQueueIterator();}private class GeneralizedQueueIterator implements Iterator<T> {private T[] temp;private int index;public GeneralizedQueueIterator() {temp = (T[]) new Object[size];for (int i = 0; i < size; i++) {temp[i] = data[i];}index = 0;}@Overridepublic boolean hasNext() {return index < size;}@Overridepublic T next() {return temp[index++];}}public static void main(String[] args) {GeneralizedQueue<Integer> queue = new GeneralizedQueue<>();queue.insert(1);queue.insert(2);queue.insert(3);queue.insert(4);for (int i : queue) {System.out.print(i + " ");}System.out.println();queue.delete(4);for (int i : queue) {System.out.print(i + " ");}System.out.println();}
}

1.3.39

import java.util.Iterator;// 对于循环队列而言，如果lo指向队头，hi指向队尾，当lo和hi相等时，无法判断队列为空还是满
public class RingBuffer<T> implements Iterable<T> {private T[] data;private int lo;     // 指向队头private int hi;     // 指向队尾元素的下一个位置public RingBuffer() {data = (T[]) new Object[10];lo = 0;hi = 0;}public RingBuffer(int capacity) {data = (T[]) new Object[capacity];lo = 0;hi = 0;}public boolean isEmpty() {return lo == hi;}public boolean isFull() {return (hi + 1) % data.length == lo;}public void enqueue(T item) {if (isFull())System.out.println("RingBuffer is full, please wait!");else {data[hi] = item;hi = (hi + 1) % data.length;}}public T dequeue() {if (isEmpty())throw new UnsupportedOperationException("RingBuffer is Empty!");T res = data[lo];lo = (lo + 1) % data.length;return res;}@Overridepublic Iterator<T> iterator() {return new RingBufferIterator();}private class RingBufferIterator implements Iterator<T> {private T[] temp;private int index;public RingBufferIterator() {int size = hi - lo;temp = (T[]) new Object[size];for (int i = 0, j = lo; i < size; i++) {temp[i] = data[j++];}index = 0;}@Overridepublic boolean hasNext() {return index < hi - lo;}@Overridepublic T next() {return temp[index++];}}public static void main(String[] args) {RingBuffer<Integer> ringBuffer = new RingBuffer<>();ringBuffer.enqueue(1);ringBuffer.enqueue(2);ringBuffer.enqueue(3);ringBuffer.enqueue(4);for (int i : ringBuffer) {System.out.print(i + " ");}System.out.println();ringBuffer.dequeue();for (int i : ringBuffer) {System.out.print(i + " ");}System.out.println();}
}

1.3.40

import java.util.Iterator;public class MoveToFront<T> implements Iterable<T> {private Node first;private int size;private class Node {T item;Node prev;Node next;public Node(T item) {this.item = item;prev = null;next = null;}}public MoveToFront() {first = null;size = 0;}public boolean isEmpty() {return size == 0;}public int size() {return size;}public void add(T item) {Node node = new Node(item);if (isEmpty())first = node;else {Node cur = first;while (cur != null) {if (cur.item == item) {if (cur == first) {first = cur.next;first.prev = null;} else if (cur.next == null) {cur.prev.next = null;} else {cur.prev.next = cur.next;cur.next.prev = cur.prev;}size--;}cur = cur.next;}node.next = first;first.prev = node;first = node;}size++;}@Overridepublic Iterator<T> iterator() {return new MoveToFrontIterator();}private class MoveToFrontIterator implements Iterator<T> {private Node temp;public MoveToFrontIterator() {temp = first;}@Overridepublic boolean hasNext() {return temp != null;}@Overridepublic T next() {T res = temp.item;temp = temp.next;return res;}}public static void main(String[] args) {MoveToFront<Integer> moveToFront = new MoveToFront<>();moveToFront.add(1);moveToFront.add(2);moveToFront.add(3);moveToFront.add(4);for (int i : moveToFront) {System.out.print(i + " ");}System.out.println();moveToFront.add(3);for (int i : moveToFront) {System.out.print(i + " ");}System.out.println();}
}

1.3.41

import java.util.Iterator;public class Queue<T> implements Iterable<T> {private Node first;private Node last;private int size;private class Node {T item;Node next;public Node(T item) {this.item = item;next = null;}}public Queue() {first = null;last = null;size = 0;}public boolean isEmpty() {return size == 0;}public int size() {return size;}public Queue(Queue<T> q) {int size = q.size();for (int i = 0; i < size; i++) {T item = q.dequeue();enqueue(item);q.enqueue(item);}}public void enqueue(T item) {Node node = last;last = new Node(item);if (isEmpty())first = last;elsenode.next = last;size++;}public T dequeue() {T item = first.item;first = first.next;if (isEmpty())last = null;size--;return item;}@Overridepublic Iterator<T> iterator() {return new QueueIterator();}private class QueueIterator implements Iterator<T> {private Node cur = first;@Overridepublic boolean hasNext() {return cur != null;}@Overridepublic T next() {T res = cur.item;cur = cur.next;return res;}}public static void main(String[] args) {Queue<Integer> q = new Queue<>();for (int i = 0; i < 10; i++) {q.enqueue(i);}Queue<Integer> r = new Queue<>(q);int size = q.size;for (int i = 0; i < size; i++) {System.out.print(q.dequeue() + " ");}System.out.println();for (int i : r) {System.out.print(i + " ");}System.out.println();}
}

1.3.42

import java.util.Iterator;public class Stack<T> implements Iterable<T> {private Node first;     // top of stack (most recently added node)private int size;          // number of itemsprivate class Node {T item;Node next;}public Stack() {first = null;size = 0;}public Stack(Stack<T> s) {Stack<T> temp = new Stack<>();while (!s.isEmpty()) {temp.push(s.pop());}while (!temp.isEmpty()) {T item = temp.pop();push(item);s.push(item);}}public boolean isEmpty() {return first == null;}public int size() {return size;}public void push(T item) {Node oldFirst = first;first = new Node();first.item = item;first.next = oldFirst;size++;}public T pop() {T item = first.item;first = first.next;size--;return item;}@Overridepublic Iterator<T> iterator() {return new ListIterator();}private class ListIterator implements Iterator<T> {private Node current = first;@Overridepublic boolean hasNext() {return current != null;}@Overridepublic T next() {T item = current.item;current = current.next;return item;}}public static void main(String[] args) {Stack<Integer> s = new Stack<>();s.push(1);s.push(2);s.push(3);s.push(4);for (int i : s) {System.out.print(i + " ");}System.out.println();Stack<Integer> t = new Stack<>(s);for (int i : t) {System.out.print(i + " ");}System.out.println();}
}

1.3.43

import java.io.File;
import java.util.Iterator;
import java.util.Scanner;public class ListingFiles implements Iterable {private FileNode first;private FileNode last;private int size;private class FileNode {String item;FileNode next;}public ListingFiles(String pathName) {generateList(pathName);}public void generateList(String pathName) {File file = new File(pathName);if (!file.isDirectory()) {FileNode newLast = new FileNode();newLast.item = file.getName();if (first == null) {first = newLast;last = newLast;} else {last.next = newLast;last = newLast;}size++;} else {File[] files = file.listFiles();for (File file1 : files) {generateList(file1.getPath());}}}@Overridepublic Iterator iterator() {return new ListingFilesIterator();}private class ListingFilesIterator implements Iterator {private FileNode cur = first;@Overridepublic boolean hasNext() {return cur != null;}@Overridepublic String next() {String s = cur.item;cur = cur.next;return s;}}public static void main(String[] args) {Scanner in = new Scanner(System.in);String pathName = in.nextLine();ListingFiles folder = new ListingFiles(pathName);for (Object o : folder) {System.out.println(o);}}
}

1.3.44

// 光标位置为左栈的栈顶指针位置，向左向右移动用栈push、pop来模拟光标的移动
public class Buffer {Stack<Character> leftStack;Stack<Character> rightStack;public Buffer() {leftStack = new Stack<>();rightStack = new Stack<>();}public void insert(char c) {leftStack.push(c);}public char delete() {return leftStack.pop();}public void left(int k) {if (k > leftStack.size())return;for (int i = 0; i < k; i++) {rightStack.push(leftStack.pop());}}public void right(int k) {if (k > rightStack.size())return;for (int i = 0; i < k; i++) {leftStack.push(rightStack.pop());}}public int size() {return leftStack.size() + rightStack.size();}public static void main(String[] args) {Buffer buffer = new Buffer();String str = "123456789";for (int i = 0; i < str.length(); i++) {buffer.insert(str.charAt(i));}buffer.left(2);System.out.print("leftStack: ");for (Character c : buffer.leftStack)System.out.print(c + " ");System.out.println();System.out.print("rightStack: ");for (Character c : buffer.rightStack)System.out.print(c + " ");System.out.println();buffer.delete();System.out.print("leftStack: ");for (Character c : buffer.leftStack)System.out.print(c + " ");System.out.println();System.out.print("rightStack: ");for (Character c : buffer.rightStack)System.out.print(c + " ");System.out.println();buffer.right(4);System.out.print("leftStack: ");for (Character c : buffer.leftStack)System.out.print(c + " ");System.out.println();System.out.print("rightStack: ");for (Character c : buffer.rightStack)System.out.print(c + " ");System.out.println();buffer.insert('2');System.out.print("leftStack: ");for (Character c : buffer.leftStack)System.out.print(c + " ");System.out.println();System.out.print("rightStack: ");for (Character c : buffer.rightStack)System.out.print(c + " ");System.out.println();}
}

1.3.45

答案请戳：练习1.3.45

1.3.46

import java.util.Scanner;public class Solution {public static void main(String[] args) {Scanner in = new Scanner(System.in);int N = in.nextInt();int[] nums = new int[N];for (int i = 0; i < N; i++) {nums[i] = in.nextInt();}if (isGenerate(nums))System.out.println("Can generate!");elseSystem.out.println("Can't generate!");}public static boolean isGenerate(int[] nums) {for (int i = 0; i < nums.length - 2; i++) {if (isForbiddenTriple(nums[i], nums[i + 1], nums[i + 2]))return false;}return true;}public static boolean isForbiddenTriple(int first, int second, int third) {if (first > second && first > third) {if (second < third)return true;}return false;}
}

1.3.47

答案请戳：练习1.3.47

1.3.48

public class MyStack<T> {private int size;private Node first;private class Node {T item;Node next;}private Deque<T> deque;public MyStack() {size = 0;first = null;}public void push(T item) {if (deque == null)deque = new Deque<T>();deque.pushRight(item);}public T pop() {return deque.popRight();}public boolean isEmpty() {return deque.isEmpty();}public int size() {return deque.size();}
}

1.3.49

可以看看stackoverflow上的讨论：How to implement a queue with three stacks?

1.3.50

import java.util.Iterator;public class Stack<T> implements Iterable<T> {private Node first;     // top of stack (most recently added node)private int size;          // number of itemsprivate int count;      // push pop countprivate class Node {T item;Node next;}public Stack() {first = null;size = 0;count = 0;}public Stack(Stack<T> s) {Stack<T> temp = new Stack<>();while (!s.isEmpty()) {temp.push(s.pop());}while (!temp.isEmpty()) {T item = temp.pop();push(item);s.push(item);}size = 0;count = 0;}public boolean isEmpty() {return first == null;}public int size() {return size;}public void push(T item) {Node oldFirst = first;first = new Node();first.item = item;first.next = oldFirst;size++;count++;}public T pop() {T item = first.item;first = first.next;size--;count++;return item;}@Overridepublic Iterator<T> iterator() {return new ListIterator();}private class ListIterator implements Iterator<T> {private Node current;private int originalCount;public ListIterator() {current = first;originalCount = count;}@Overridepublic boolean hasNext() {return current != null;}@Overridepublic T next() {if (originalCount != count)throw new java.util.ConcurrentModificationException();T item = current.item;current = current.next;return item;}}
}