引言
因为其他文章中用到了栈和队列,有时会进行改动。因此把实现贴在这里。
暂且不分析实现原理。
栈的实现
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
;
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("[");
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();
}
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
;
}
}
}
转载请注明原文地址: https://yun.8miu.com/read-25654.html