普林斯顿算法课第二周-queue

和queue和stack具有相同的数据结构,但是其不同点在于删除元素的方法,stack移除元素的操作是移除stack中最顶部的元素,而queque则是移除最底部的元素.总结起来:stack是后进先出,queque是先进先出.

基础知识回顾

queque

queque就像是我们日常生活中order的场景,当我们买票时,先进入队列的人,先买到票,而后离开队列,新加入的人则按照规则排在队列的最后.queque一般包含如下方法:

1. dequeue() 从队列中移除元素
2. enqueue() 向队列中添加元素
3. isEmpty() 检查是否为空

queue的实现

使用链表实现queque

使用链表实现queque的方法和链表实现stack的方法大同小异,我的这篇文章描述了stack的实现.下面的java代码描述了如何使用链表实现queque.

package com.andy.algorithms;

public class LinkedQueueofString {
    /*
    * 是用链表实现一个queue
    * queue的规则是先进先出,中文叫做队列
    * 添加新元素的方法叫做:enqueue
    * 移除元素的方法叫做:dequeue
    * */

    private Node item;
    private Node first, last;

    public boolean isEmpty(){
        return first == null;
    }

    public void enqueue(String item) {
        /*
        * 入队操作的时候,新的元素被放在表的末端
        * 项链表添加新的last节点,执行null
        * 老的last,指向新的last
        * */
        Node oldlast = last;
        last = new Node();
        last.item = item;
        last.next = null;
        //如果向空空队列中添加元素,此时last即是first
        if(isEmpty())   first = last;
        else            oldlast.next = last;
    }

    public String dequeue(){
        String item = first.item;
        first = first.next;
        //为了保证取出最后一个元素后,队列是空的,设置last为null
        if(isEmpty())   last=null;
        return item;
    }


    private class Node{
        private String item;
        private Node next;
    }
}