算法笔记－队列和栈

先进先出队列（或简称队列）

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

典型的先进先出队列

队列的API:

public class Queue<Item> implements Iterable<Item>
               Queue()                                   创建空队列
         void  enqueue(Item item)                        添加一个元素
         Item  dequeue()                                 删除最早添加的元素
       boolean isEmpty()                                 队列是否为空
           int size()                                    队列中的元素数量

队列的链表实现

import java.util.Iterator;
public class Queue<Item> implements Iterable<Item> {
    
    private class Node{
        //定义节点嵌套类
        Item item;
        Node next;
    }
    
    private Node first;//指向最早添加的节点的链接
    private Node last;//指向最近添加的节点的链接
    private int count;//队列中元素的数量
    
    
    public Queue(){
        first = null;
        last = null;
        count = 0;
    }
    
    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;
        count++;
    }
    
    public Item dequeue(){
        //从表头删除元素
        if (isEmpty()){
            return null;
        }
        
        Item item = first.item;
        first = first.next;
        count--;
        if (isEmpty())last = null;
        return item;
    }
    
    public boolean isEmpty(){
        return count==0;
    }
    
    public int size(){
        return count;
    }
    
    @Override
    public Iterator<Item> iterator() {
        return new QueueIterator();
    }
    
    private class QueueIterator implements Iterator<Item>{
        
        @Override
        public boolean hasNext() {
            return !isEmpty();
        }
        
        @Override
        public Item next() {
            return dequeue();
        }
    }
}

下压栈（或简称栈）

是一种基于后进先出（LIFO）策略的集合类型

下压栈上的操作

栈的API：

/*
 * public class Stack<Item> implements Iterable<Item>
 *              Stack()                        创建一个空栈
 *         void push(Item item)                添加一个元素
 *         Item pop()                          删除最近添加的一个元素
 *      boolean isEmpty()                      栈是否为空
 *          int size()                         栈中元素的数量
 * */

栈的链表实现

import java.util.Iterator;
public class Stack<Item> implements Iterable<Item>{
    
    private class Node{
        //定义了节点嵌套类
        Item item;
        Node next;
    }
    
    private Node first; //栈顶,最近添加的元素
    private int count; //栈中元素的数量
    
    //无参构造方法
    public Stack(){
        first = null;
        count = 0;
    }
    
    public void push(Item item){
        Node oldFirst = first;
        first = new Node();
        first.item = item;
        first.next = oldFirst;
        count++;
    }
    
    public Item pop(){
        if (isEmpty()) return null;
        
        Item item = first.item;
        first = first.next;
        count--;
        return item;
    }
    
    public boolean isEmpty(){
        return count == 0;
    }
    
    public int size(){
        return count;
    }
    
    @Override
    public Iterator<Item> iterator() {
        return new StackIterator<Item>();
    }
    
    private class StackIterator<Item> implements Iterator<Item>{
        
        @Override
        public boolean hasNext() {
            return !isEmpty();
        }
        
        @Override
        public Item next() {
            return (Item) pop();
        }
    }
    
}

挑战------用有限个栈实现一个队列

解答：用两个栈实现一个队列，栈0专门用来push，栈1专门用来pop，每当需要dequeue的时候，就将栈0中的元素放入栈1中，然后就可以将先进入队列的元素pop出来了，如果需要连续pop那就直接pop就行，让后在需要enqueue的时候就将栈1中的元素push回栈0，然后就可以继续push了。虽然中间遇到多次迷之bug，但是好歹也是敲出来了😭，果然在开始敲代码之前先理清一下思路比较好，下面上代码：

import java.util.Iterator;

/**
 * public class Queue<Item> implements Iterable<Item>
 *               Queue()                                   创建空队列
 *         void  enqueue(Item item)                        添加一个元素
 *         Item  dequeue()                                 删除最早添加的元素
 *       boolean isEmpty()                                 队列是否为空
 *           int size()                                    队列中的元素数量
 */
public class Squeue<Item> implements Iterable<Item>{
    
    private Stack<Item>[] stacks;
    private int count;
    
    public Squeue(){
        stacks = new Stack[2];
        stacks[0] = new Stack<Item>();
        stacks[1] = new Stack<Item>();
        count = 0;
    }
    
    public void enqueue(Item item){
        if (stacks[0].size() == 0&&count!=0){
            for (int i = 0;i < count; i++){
                stacks[0].push(stacks[1].pop());
            }
        }
        stacks[0].push(item);
        System.out.println(item);
        count++;
        System.out.println(count);
    }
    
    public Item dequeue(){
        if (isEmpty()) return null;
        if (stacks[0].size()==0) {
            count--;
            return stacks[1].pop();
        }
        
        for (int i = 0; i < count; i++){
            stacks[1].push(stacks[0].pop());
        }
        
        Item item = stacks[1].pop();
        count--;
        System.out.println(count);
        return item;
    }
    
    public boolean isEmpty(){
        return count==0;
    }
    
    public int size(){
        return count;
    }
    
    
    @Override
    public Iterator<Item> iterator() {
        return new SIterator<>();
    }
    
    private class SIterator<Item> implements Iterator<Item>{
        
        @Override
        public boolean hasNext() {
            return !isEmpty();
        }
        
        @Override
        public Item next() {
            return (Item) dequeue();
        }
    }
}
aha!忘了写注释

讨论一下队列和栈的链表实现和数组实现

链表实现因为要创建新对象调整关系等导致了总的来说速度要慢于数组实现，但数组实现中会不时因为数组大小的调整而出现一次缓慢操作，这样就使得需要稳定快速的操作的情况下数组实现不合适，但是如果只考虑总的时间消耗的话，数组实现是要更快的。

资源及参考

本笔记是学习普林斯顿大学算法课程以及阅读其教材《算法》第四版所作