欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

栈及队列的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;
        }
    }
}