普林斯顿Algorithms-1.3.2-包、队列、栈的链表实现

Linked lists

 A linked list is a recursive data structure that is either empty (null) or a reference to a node having a generic item and a reference to a linked list. To implement a linked list, we start with a nested class that defines the node abstraction

Linked-list implementations of collections.

Linked list implementation of a stack. Stack.java implements a generic stack using a linked list. It maintains the stack as a linked list, with the top of the stack at the beginning, referenced by an instance variable first. To push() an item, we add it to the beginning of the list; to pop() an item, we remove it from the beginning of the list.

定义栈顶节点和n两个成员变量，创建Node类 push/pop：将栈顶节点更新，改变n

Linked list implementation of a queue. Program Queue.java implements a generic FIFO queue using a linked list. It maintains the queue as a linked list in order from least recently to most recently added items, with the beginning of the queue referenced by an instance variable first and the end of the queue referenced by an instance variable last. To enqueue() an item, we add it to the end of the list; to dequeue() an item, we remove it from the beginning of the list.

Linked list implementation of a bag. Program Bag.java implements a generic bag using a linked list. The implementation is the same as Stack.java except for changing the name of push() to add() and removing pop().

如何实现迭代写法？？？

To implement iteration in a collection:

Include the following import statement so that our code can refer to Java's java.util.Iterator interface:

import java.util.Iterator;

Add the following to the class declaration, a promise to provide an iterator() method, as specified in the java.lang.Iterableinterface:

implements Iterable<Item>

Implement a method iterator() that returns an object from a class that implements the Iterator interface:

public Iterator<Item> iterator() {

    return new ListIterator();

}

课后问答

Autoboxing Q + A 泛型Q + A

课后练习

Write a stack client Parentheses.java that reads in sequence of left and right parentheses, braces, and brackets from standard input and uses a stack to determine whether the sequence is properly balanced. 

For example, your program should print true for [()]{}{[()()]()} and false for [(]).