栈和队列的数组和链表实现--算法第四版笔记

所有栈和队列都可以用同一种数据结构实现，只不过是读取写入顺序不一样。

比如Java标准库中的Stack类，继承自Vector类。可以使用数组操作insert和remove方法在任何地方进行插入和删除，尽管这违背了栈设计的初衷。

数组栈

public class ArrayStack<Item> {
    private Item[] a;
	private int N;

	public ArrayStack(int cap) 
    {
        a = (Item[]) new Object[cap];
	}
    public void push(Item item) 
    {
		a[N++] = item;
	}
	public Item pop() 
    {
		return a[--N];
	}
}

数组队列
数组实现队列，有些麻烦

public class ArrayQueue<Item> {
    private Item[] a;
    private int size = 0;
    private int begin = 0;
    private int end = 0;

    public ArrayQueue(int cap)
    {
        a = (Item[]) new Object[cap]; //因为Java泛型类型擦除，不能写 a = new Item[cap];
    }
    public void enqueue(Item item) { 
        //入队
        if (size == a.length)
            throw new RuntimeException("队列已满");
        size++;
        a[end++] = item;
        if (end == a.length)  end = 0; //队尾移动到数组末尾，移动至数组开头
    }
    public Item dequeue() { 
        //出队
        if (size == 0)
            throw new RuntimeException("队列已空");
        size--;
        Item t = a[begin++]; //保存a[begin]的值，begin的值可能在返回前置0
        if (begin == a.length)  begin = 0; //队首移动到数组末尾，移动至数组开头
        return t;
    }
}

链表栈

public class LinkedListStack<Item> {
    private Node first;
    private int N;
    private class Node
    {   //链表节点
        Item item;
        Node next;
    }
    public void push(Item item)
    {
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
        N++;
    }
    public Item pop()
    {
        Item item = first.item;
        first = first.next;
        N--;
        return item;
    }
}

链表队列

public class LinkedListQueue<Item> {
    private Node first;
    private Node last;
    private int N;
    private class Node
    {   //定义链表节点
        Item item;
        Node next;
    }
    public void enqueue(Item item)
    {
        Node oldfirst = first;
        last = new Node();
        last.item = item;
        last.next = null;
        if (first == null) first = last;
        else               oldfirst.next = last;
        N++;
    }
    public Item dequeue()
    {
        Item item = first.item;
        first = first.next;
        if (first == null) last = null;
        N--;
        return item;
    }
}