首页Algorithms, Part I

栈和队列可以说是最基本的数据结构了，它们都是在两端进行操作，其中栈在栈顶进行操作，被称为先进后出（LIFO），队列在队头和队尾进行操作，被称为先进先出（FIFO）

# 栈

直接来看看 API 吧：

# API

public class Stack
Stack() 构造一个空栈
void push(Item item) 入栈
Item pop() 出栈
boolean isEmpty() 判空
int size() 大小

# 链栈

顾名思义，基于链表实现的栈

其中的一个结点：

private class Node {
    Item item;
    Node next;
}

完整代码：

public class LinkedStack<Item> {
    private Node first = null;
    private class Node {
        Item item;
        Node next;
    }
    public boolean isEmpty() { 
        return first == null; 
    }
    public void push(Item item) {
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
    }
    public Item pop() {
        Item item = first.item;
        first = first.next;
        return item;
    }
}

# 顺序栈

基于数组（顺序表）实现的栈是顺序栈

简单实现一个定长的栈：

public class FixedCapacityStack<Item> {
    private Item[] s;
    private int N = 0;
    public FixedCapacityStack(int capacity) { 
        s = (Item[]) new Object[capacity]; 
    } 
    public boolean isEmpty() { 
        return N == 0; 
    }
    public void push(Item item) { 
        s[N++] = item; 
    }
    public Item pop() { 
        return s[--N]; 
    }
}
但是定长的栈需要获取 capacity ，而这又需要客户端提供，然而大部分时间客户端是不知道所需的容量的。


于是就有了动态长度的栈：


# ResizingArrayStack


public class ResizingArrayStack<Item> {
    private Item[] s;
    private int N = 0;
    public ResizingArrayStack() { 
        s = (Item[]) new Object[1]; 
    } 
    public void push(Item item) {
        if (N == s.length) resize(2 * s.length);
        s[N++] = item;
    }
    public Item pop() { 
        return s[--N]; 
        s[N] = null;
        if (N > 0 && N == s.length/4) resize(s.length/2);
        return item;
    }
    private void resize(int capacity) {
        Item[] copy = (Item[]) new Object[capacity];
        for (int i = 0; i < N; i++)
            copy[i] = s[i];
        s = copy;
    }
}
此时 pop  和 push  操作的最坏时间复杂度也是O(N)O(N)。


# 迭代器


我们可以为栈写一个迭代器：


需要实现 Iterator<>  接口的 hasNext  和 next  方法，栈类也需要实现 Iterable<>  接口


public Iterator<Item> iterator() {
        return new ListIterator();
    }
    private class ListIterator implements Iterator<Item> {
        private Node current = first;
        public boolean hasNext() {
            return current != null;
        }
        public Item next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
public Iterator<Item> iterator() {
        return new ArrayIterator();
    }
    private class ArrayIterator implements Iterator<Item> {
        private int i = N;
        public boolean hasNext() {
            return i > 0;
        }
        public Item next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            return s[--N];
        }
    }
# 队列


队列是一种基于先进先出（FIFO）策略的集合类型


# API






public class Queue







Queue()
构造一个空队列




void enqueue(Item item)
入队




Item dequeue()
出队




boolean isEmpty()
判空




int size()
大小






# 链队


直接贴代码，没什么好说的


public class LinkedQueue<Item> implements Iterable<Item>{
    private Node first, last;
    private class Node {
        Item item;
        Node next;
    }
    public boolean isEmpty() { 
        return first == 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;
    }
    public Item dequeue() {
        Item item = first.item;
        first = first.next;
        if (isEmpty()) last = null;
        return item;
    }
    
    public Iterator<Item> iterator() {
        return new ListIterator();
    }
    
    private class ListIterator implements Iterator<Item> {
        private Node current = first;
        
        public boolean hasNext() {
            return current != null;
        }
        
        public Item next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
}
# 顺序队列


顺序队列是基于顺序表的队列，其实一般都是循环队列，就是栈顶、栈底两个指针， front = (front + 1) ％ MaxSize ， rear = (rear + 1) ％ MaxSize


    

  • 队空条件： rear == front
    • 

  • 队满条件： (rear + 1) % MaxSize == front
    • 

  • 元素进队： rear = (rear + 1) % MaxSize
    • 

  • 元素出队： front = (front + 1) % MaxSize
    • 



public void push(Item item)	{ 
   if ((rear + 1) % MaxSize == front) return;
   rear = (rear + 1) % MaxSize;
   s[rear] = item;
}
public Item pop() {  
   if (front == rear) throw new NoSuchElementException();
   front = (front + 1) % MaxSize;
   return s[front];
}