引言

因为其他文章中用到了栈和队列，有时会进行改动。因此把实现贴在这里。

暂且不分析实现原理。

栈的实现

package com.algorithms.stack; import java.util.ConcurrentModificationException; import java.util.Iterator; import java.util.NoSuchElementException; import java.util.Objects; /** * 采用头插法插入链表的栈的实现 */ public class Stack<Item> implements Iterable<Item>{ private Node first; //指向链表的头结点 private int sz;//size of stack private int modCount = 0; public Stack(){ first = null; sz = 0; } public void push(Item item) { Node newNode = new Node(); newNode.item = item; newNode.next = first; first = newNode; modCount++; } public Item pop() { Objects.requireNonNull(first); Item item = first.item; first = first.next; modCount++; return item; } public Item peek() { Objects.requireNonNull(first); return first.item; } public boolean isEmpty() { return first == null; } public int size() { return sz; } @Override public Iterator<Item> iterator() { return new LinkedIterator(first); } private class LinkedIterator implements Iterator<Item> { private int expectedModCount = modCount; private Node cur; private LinkedIterator(Node p) { this.cur = p; } @Override public boolean hasNext() { return cur !=null; } @Override public Item next() { if (expectedModCount != modCount) { throw new ConcurrentModificationException(); } if (!hasNext()) { throw new NoSuchElementException(); } Item item = cur.item; cur = cur.next; return item; } } private class Node{ Item item; Node next; } }

队列的实现

package com.algorithms.queue; import java.util.Iterator; public class Queue<Item> implements Iterable<Item> { /** * 队列中元素个数 */ private int sz = 0; /** * 指向队头和队尾 */ private Node<Item> first, last; public Queue() { first = last = null; } public void enqueue(Item item) { Node<Item> oldlast = last; last = new Node<>(item); if (isEmpty()) { first = last; } else { oldlast.next = last; } sz++; } public Item dequeue() { if (isEmpty()) { throw new RuntimeException("the queue is empty!"); } Item item = first.item; first = first.next; if (first == null) last = null; sz--; return item; } public boolean isEmpty() { return sz == 0; } public int size() { return sz; } @Override public String toString() { StringBuilder sb = new StringBuilder("["); //实现了Iterable就可以用foreach循环啦 int i = 0; for (Item item : this) { if (i++ == size() - 1) { //提前返回 return sb.append(item).append("]").toString(); } sb.append(item).append(" "); } return sb.append("]").toString(); } @Override public Iterator<Item> iterator() { return new ListIterator(); } /** * 这里推荐使用嵌套类而不是内部类 * * @param <Item> */ private static class Node<Item> { Item item; Node<Item> next; Node(Item item, Node<Item> next) { this.item = item; this.next = next; } Node(Item item) { this(item, null); } } /** * 这里要使用内部类，与外部类实例建立联系，不同的实例返回的迭代器不同 */ private class ListIterator implements Iterator<Item> { private Node<Item> current = first; @Override public boolean hasNext() { return current != null; } @Override public Item next() { Item item = current.item; current = current.next; return item; } } }