栈及队列的Java简单实现
程序员文章站
2022-07-10 20:31:03
...
引言
因为其他文章中用到了栈和队列,有时会进行改动。因此把实现贴在这里。
暂且不分析实现原理。
栈的实现
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 first, last;
public Queue() {
first = last = null;
}
public void enqueue(Item item) {
Node oldlast = last;
last = new Node();
last.item = item;
last.next = null;
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 + " ");
}
return sb.append("]").toString();
}
@Override
public Iterator<Item> iterator() {
return new ListIterator();
}
private class Node {
Item item;
Node next;
}
private class ListIterator implements Iterator<Item> {
private Node current = first;
@Override
public boolean hasNext() {
return current != null;
}
@Override
public Item next() {
Item item = current.item;
current = current.next;
return item;
}
}
}
上一篇: 一日游爬山需要带什么吃的