棧
public interface Stack<Item> extends Iterable<Item> {
? ? boolean isEmpty();
? ? int size();
? ? Stack<Item> push(Item item);
? ? Item pop() throws Exception;
}
1.數(shù)組實現(xiàn)
public class ResizingArrayStack<Item> implements Stack<Item> {
? ? ?private Item[] a = (Item[]) new Object[1];
? ? ?private int N = 0;
?@Override? //判斷是否為空
????public boolean isEmpty() {
? ? ? ? ? ? return N == 0;
? ?}
?@Override
? ?public int size() { //獲得數(shù)組長度
? ? ? ? ? return N;
? ? }
? ?private void resize(int max) { //調(diào)整數(shù)組大小，使得棧具有伸縮性
? ? ? ?Item[] temp = (Item[]) new Object[max];
? ? ? ?for(int i = 0; i < N; i++) {
? ? ? ? ? ? ? ?temp[i] = a[i];
? ? ? ?}
? ? ? ? ?a = temp;
? ? }
@Override??
????public Stack<Item> push(Item item) { //入棧操作
? ? ? ? ? if (N == a.length)? resize(2*N);
? ? ? ? ? a[N++] = item;
? ? ? ? ? return this;
????}
@Override
public Item pop() throws Exception {//出棧操作
if (isEmpty())
? ? ? ? ? throw new Exception("Stack is empty!");
Item item = a[--N];
a[N] = null; // 避免對象游離
return item;
}
private void check(){
? ? ? if (N > 0 && N == a.length/4){
? ? ? ? ? ? ? ? ? resize(a.length/2);
? ? ? ? }else if (N>a.lenth){
? ? ? ? ? ? ? ? ? resize(a.length*2)
? ? ? ? ? }
}
@Override
public Iterator<Item> iterator(){// 返回逆序遍歷的迭代器
? ? ? ? ? return new Iterator<Item>() {
? ? ? ? ? ? ? ? ? ?private int i = N;
? ? ? ? ? ?public boolean hasNext() {
? ? ? ? ? ? ? ? ? ? ?return i > 0;
? ? ? ? ? ?}
? ? ? ? ? ?public Item next() {
? ? ? ? ? ? ? ? ? ?return a[--i];
? ? ? ? ? ?}
? ? ? ? ? ? public void remove() {}
? ? ?};
? }
}
2.鏈表實現(xiàn)
需要使用鏈表的頭插法來實現(xiàn)，因為頭插法中最后壓入棧的元素在鏈表的開頭，它的 next 指針指向前一個壓入棧的元素，在彈出元素時就可以通過 next 指針遍歷到前一個壓入棧的元素從而讓這個元素成為新的棧頂元素.
public class ListStack<Item> implements Stack<Item> {
????????private Node top = null;
????????private int N = 0;
????????private class Node{
????????????Item item;
????????????Node next;
????????}
@Override
????????public boolean isEmpty() {
? ? ? ? ? ? ?return top == null;
? ? ? ? }
@Override
? ? ? ?public int size() {
? ? ? ? ? ? ? return N;
? ? ? ?}
@Override
? ? ? public Stack<Item> push(Item item) {
? ? ? ? ? ? ? Node newTop = new Node();
? ? ? ? ? ? ? newTop.item = item;
? ? ? ? ? ? ? newTop.next = top;
? ? ? ? ? ? ?top = newTop;
? ? ? ? ? ? ?N++;
? ? ? ? ? ? return this;
? ?}
@Override
? public Item pop() throws Exception {
????????if (isEmpty()){
????????????????throw new Exception("Stack is empty!");
? ? ? ? ?}?
????????Item item = top.item;
????????top = top.next;
????????N--;
????????return item;
? }??
@Override
public Iterator<Item> iterator() {
? ? ? return new Iterator<Item>() {// 返回鏈表遍歷的迭代器
? ? ? ? ? ? ? ?private Node current = top;
? ? ? ? ? ? ? public boolean hasNext() {
? ? ? ? ? ? ? ? ? ? ? ?return current != null; // current.next != null; 錯誤
? ? ? ? ? ? ?}
? ? ? ? ? ? ?public Item next() {
? ? ? ? ? ? ? ? ? ? ? Item item = current.item;? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ?current = current.next;
? ? ? ? ? ? ? ? ? ? ?return item;
? ? ? ? ? ? ? ?}
? ? ? ? ? ? ?public void remove() {}
? ? ? ? };
? ? }
}
隊列
下面是隊列的鏈表實現(xiàn)，需要維護 first 和 last 節(jié)點指針，分別指向隊首和隊尾。
這里需要考慮 first 和 last 指針哪個作為鏈表的開頭。因為出隊列操作需要讓隊首元素的下一個元素成為隊首，所以需要容易獲取下一個元素，而鏈表的頭部節(jié)點的 next 指針指向下一個元素，因此可以讓 first 指針鏈表的開頭。
public interface Queue<Item> extends Iterable<Item> {
? ? ? ? boolean isEmpty();
????????int size();? ??
????????Queue<Item>? add (Item item);
????????Item remove() throws Exception;
}
```
```
public class ListQueue<Item> implements Queue<Item> {
????????private Node first;
????????private Node last;
????????private int N = 0;
????????private class Node {
????????????????Item item;
????????????????Node next;
????????}
@Override
????????public boolean isEmpty() {
????????????????return first == null;
? ? ? ? ?}
@Override
????????public int size() {
? ? ? ? ? ? ? ? return N;
????????}
@Override
? ? ? ? ?public Queue<Item> add (Item item){
? ? ? ? ? ? ? ? Node newNode = new Node();
????????????????newNode.item = item;
????????????????newNode.next = null;
????????????????if (isEmpty()){
? ? ? ? ? ? ? ? ? ?????first = newNode;
? ? ? ? ? ? ? ? ?} else{
????????????????????????last.next = newNode;
????????????????????????last = newNode;\
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ?N++;
? ? ? ? ? ? ? ? return this;
}
@Override
????????public Item remove () throws Exception {
????????????????if (isEmpty())
????????????????????????throw new Exception("Queue is empty!");
????????????????NODE node = first.item;
????????????????first = first.next;
?????????????????N--;
????????????????if (isEmpty()){
????????????????????????last = null;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? return node.item;? ? ? ??
}
@Override
????public Iterator<Item> iterator(){
????????????return new Iterator<Item>() {
? ? ? ? ? ? ????????? Node current = first;
? ? ? ? ? ? ? ? ? ? ? public boolean hasNext() {
????????????????????????????????return current != null;
? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? ? public Item next() {
????????????????????????????????Item item = current.item;
????????????????????????????????current = current.next;
????????????????????????????????return item;
? ? ? ? ? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ? ? ? ? ?public void remove() {}
? ? ? ? ? ? ? };
????????}
}
