美文网首页算法与数据结构
算法与数据结构系列之[队列]

算法与数据结构系列之[队列]

作者: 秦老厮 | 来源:发表于2019-06-05 14:20 被阅读6次

    上一篇介绍了栈这种数据结构，栈是从线性表的表尾进并从表尾出，即后进先出，先进后出，若是银行排队采用这种方式，估计先去的人都气死了。那么有没有先进先出，类似于银行排队这种方式的数据结构呢？答案是肯定的，队列就是这样先进先出(FIFO)的数据结构，只允许一端进行插入操作，另一端进行删除操作，允许插入的一端叫做队尾，删除操作的一端叫做队头。队列也有两种实现方式，可以采用动态数组实现，也可以使用单链表实现，其实现方式各有优缺点。但队列和栈不同之处在于采用动态数据实现时，入队从队尾进入，出队要在队首进行，即每次出队，队列中所有元素都要向前移动，以保证队列的队头，也就是下标为0的位置不为空，此时的时间复杂度是O(n),对性能有一定影响，所有需要用到循环队列来解决这一问题。关于循环队列的具体细节请参考数据结构的有关书籍，这里贴出代码，以供参考。
    C语言代码：
    1.Queue.c

    #include <stdio.h>
#include <stdlib.h>

typedef int QElemType;
typedef int Status;

#define QUEUE_INIT_SIZE 100   //初始分配的存储空间大小
#define INCREMENT 10     //存储空间分配增量
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0

//循环队列
typedef struct {
    QElemType *data; //声明了一个名为data的长度不确定的数组，也叫“动态数组”
    int front;  //头指针
    int tail;  //尾指针
    int length; //维护一个队列分配的内存大小
}Queue;

/**
 * 初始化一个队列
 * @param Q
 * @return
 */
Status InitQueue(Queue *Q){
    Q->data = (QElemType *)malloc(QUEUE_INIT_SIZE * sizeof(QElemType));
    if(!Q->data)
        exit(-1);
    Q->front = 0;
    Q->tail =0;
    Q->length = QUEUE_INIT_SIZE;
    return OK;
}

/**
 * 返回队列的大小
 * @param Q
 * @return
 */
int GetQueueSize(Queue Q){
    return (Q.tail - Q.front + Q.length) % Q.length;
}

/**
 * 判断队列是否为空
 * @param Q
 * @return
 */
int IsQueueEmpty(Queue Q){
    if(Q.front == Q.tail)
        return TRUE;
    return FALSE;
}

/**
 * 循环队列入队
 * @param Q
 * @param e
 * @return
 */
Status EnQueue(Queue *Q,QElemType e){
    if((Q->tail+1) % Q->length == Q->front){ //队列已满，进行扩容
        Q->data = (QElemType *) realloc(Q->data,(Q->length + INCREMENT) * sizeof(QElemType));
        Q->length += INCREMENT;
    }
    if(!Q->data)  //分配内存失败
        exit(-1);
    Q->data[Q->tail] = e;
    Q->tail = (Q->tail + 1) % Q->length;
    return OK;
}

/**
 * 循环队列出队
 * @param Q
 * @param e
 * @return
 */
Status DeQueue(Queue *Q,QElemType *e){
    if(Q->front == Q->tail)  //队列为空
        return ERROR;
    *e = Q->data[Q->front];
    Q->front = (Q->front + 1) % Q->length;

    return OK;
}

/**
 * 遍历输出队列元素
 * @param queue
 */
void DisplayQueue(Queue queue){
    if(IsQueueEmpty(queue))
        printf("队列为空");
    for (int i = queue.front; i != queue.tail; i =(i+1) % queue.length) {
        printf("%d",queue.data[i]);
    }
    printf("\n");
}

//链表队列的实现
typedef struct QNode{
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr;

typedef struct {
    QueuePtr front,tail;
    int size;
}LinkQueue;

/**
 * 初始化一个链表队列
 * @param L
 * @return
 */
Status InitLinkQueue(LinkQueue *L){
    L->front = L->tail = (QueuePtr)malloc(sizeof(QNode));
    if(!L->front)
        exit(-1);
    L->front->next = NULL;
    L->size = 0;
    return OK;
}

/**
 * 返回链表队列的长度
 * @param linkQueue
 * @return
 */
int GetLinkQueueSize(LinkQueue linkQueue){
    return linkQueue.size;
}

/**
 * 判断链表队列是否为空
 * @param linkQueue
 * @return
 */
int IsLinkQueueEmpty(LinkQueue linkQueue){
    if(linkQueue.size == 0)
        return TRUE;
    return FALSE;
}

/**
 * 链表栈的入栈
 * @param Q
 * @param e
 * @return
 */
Status EnLinkQueue(LinkQueue *Q,QElemType e){
    QueuePtr  s = (QueuePtr)malloc(sizeof(QNode));
    if(!s)
        exit(-1);
    s->data = e;
    s->next = NULL;
    Q->tail->next = s;
    Q->tail = s;
    Q->size++;
    return OK;
}

/**
 * 链表队列的出队
 * @param Q
 * @param e
 * @return
 */
Status DeLinkQueue(LinkQueue *Q,QElemType *e){
    QueuePtr p;
    if(Q->front == Q->tail)  //队列为空
        return ERROR;
    p = Q->front->next;
    *e = p->data;
    Q->front->next = p->next;
    if(Q->tail == p)   //如果队列只有一个元素，删除一个元素后让队列的队尾指向链表头结点
        Q->tail = Q->front;
    free(p);
    Q->size--;
    return OK;
}

/**
 * 遍历输出链表队列的元素
 * @param linkQueue
 */
void DisplayLinkQueue(LinkQueue linkQueue){
    if(GetLinkQueueSize(linkQueue) == 0)
        printf("链表队列为空");
    QueuePtr q = linkQueue.front->next;
    while (q){
        printf("%d",q->data);
        q = q->next;
    }
    printf("\n");
}

    2.Queue.h

    typedef int QElemType;
typedef int Status;

//循环队列
typedef struct {
    QElemType *data; //声明了一个名为data的长度不确定的数组，也叫“动态数组”
    int front;  //头指针
    int tail;  //尾指针
    int length; //维护一个队列分配的内存大小
}Queue;

//初始化一个队列
Status InitQueue(Queue *Q);

//返回队列的大小
int GetQueueSize(Queue Q);

//判断队列是否为空
int IsQueueEmpty(Queue Q);

//循环队列入队
Status EnQueue(Queue *Q,QElemType e);

//循环队列出队
Status DeQueue(Queue *Q,QElemType *e);

//遍历输出队列元素
void DisplayQueue(Queue queue);

//链表队列的实现
typedef struct QNode{
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr;

typedef struct {
    QueuePtr front,tail;
    int size;
}LinkQueue;

//初始化一个链表队列
Status InitLinkQueue(LinkQueue *L);

//返回链表队列的长度
int GetLinkQueueSize(LinkQueue linkQueue);

//判断链表队列是否为空
int IsLinkQueueEmpty(LinkQueue linkQueue);

//链表栈的入栈
Status EnLinkQueue(LinkQueue *Q,QElemType e);

//链表队列的出队
Status DeLinkQueue(LinkQueue *Q,QElemType *e);

//遍历输出链表队列的元素
void DisplayLinkQueue(LinkQueue linkQueue);

    3.main.c

    //循环队列
    //初始化一个空的队列
    Queue queue;
    InitQueue(&queue);
    DisplayQueue(queue);
    //队列是否为空
    printf("%d",IsQueueEmpty(queue));
    printf("\n");
    //队列入队
    EnQueue(&queue,4);
    EnQueue(&queue,5);
    EnQueue(&queue,6);
    DisplayQueue(queue);
    //输出队列长度
    printf("%d",GetQueueSize(queue));
    printf("\n");
    //队列是否为空
    printf("%d",IsQueueEmpty(queue));
    printf("\n");
    //队列出队
    int num;
    int n = &num;
    DeQueue(&queue,n);
    DisplayQueue(queue);
    printf("%d",num);
    printf("\n");
    printf("---------------------------------------------");
    printf("\n");
    //链表队列
    //初始化一个链表队列
    LinkQueue linkQueue;
    InitLinkQueue(&linkQueue);
    DisplayLinkQueue(linkQueue);
    //链表队列入队
    EnLinkQueue(&linkQueue,7);
    EnLinkQueue(&linkQueue,8);
    EnLinkQueue(&linkQueue,9);
    DisplayLinkQueue(linkQueue);
    //输出链表队列长度
    printf("%d",GetLinkQueueSize(linkQueue));
    printf("\n");
    //链表队列是否为空
    int result = IsLinkQueueEmpty(linkQueue);
    if(result == 0)
        printf("false");
    if(result == 1)
        printf("true");
    printf("\n");
    //链表队列出队
    int element;
    int *e = &element;
    DeLinkQueue(&linkQueue,e);
    printf("%d",*e);
    printf("\n");
    DisplayLinkQueue(linkQueue);

    4.运行结果

    队列为空
1
456
3
0
56
4
---------------------------------------------
链表队列为空
789
3
false
7
89

    java代码：
    1.Queue.java

    public interface Queue<E> {
    int getSize();
    boolean isEmpty();
    void enqueue(E e);
    E dequeue();
    E getFront();
}

    2.ArrayQueue.java

    /**
 * 用动态数组实现队列
 * @param <E>
 */
public class ArrayQueue<E> implements Queue<E> {

    private Array<E> array; //声明数组

    public ArrayQueue(int capacity){
        array = new Array<>(capacity);
    }

    public ArrayQueue(){
        array = new Array<>();
    }
    //队列大小
    @Override
    public int getSize() {
        return array.getSize();
    }
    //判断队列是否为空
    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }
    //入队
    @Override
    public void enqueue(E e) {
        array.add(e);
    }
    //出队
    @Override
    public E dequeue() {
        return array.remove(0);
    }
    //获取队列的首个元素
    @Override
    public E getFront() {
        return array.get(0);
    }
    //队列容量
    public int getCapacity(){
        return array.getCapacity();
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Queue: ");
        res.append("front [");
        for (int i = 0; i <array.getSize() ; i++) {
            res.append(array.get(i));
            if(i != array.getSize()-1){
                res.append(",");
            }
        }
        res.append("] tail");
        return res.toString();
    }

    public static void main(String[] args) {
        ArrayQueue<Integer> arrayQueue = new ArrayQueue();
        for (int i = 0; i < 10; i++) {
            arrayQueue.enqueue(i);
            System.out.println(arrayQueue);

            if(i % 3 ==2){
                arrayQueue.dequeue();
                System.out.println(arrayQueue);
            }
        }
    }
}

    3.LoopQueue.java

    public class LoopQueue<E> implements Queue<E> {

    private int size;
    private E[] data;
    private int front,tail;

    public LoopQueue(int capacity){
        data = (E[]) new Object[capacity +1];
        front = 0;
        tail = 0;
        size = 0;
    }

    public LoopQueue(){
        this(10);
    }
    //获取循环队列容量
    public int getCapacity(){
        return data.length -1;
    }
    //获取循环队列大小
    @Override
    public int getSize() {
        return size;
    }
    //判断循环队列是否为空
    @Override
    public boolean isEmpty() {
        return front == tail;
    }
    //循环队列入队
    @Override
    public void enqueue(E e) {
        if((tail + 1) % data.length == front){
            resize(getCapacity() * 2);
        }
        data[tail] = e;
        tail = (tail + 1) % data.length;
        size++;
    }
    //循环队列出队
    @Override
    public E dequeue() {
        if(isEmpty()){
            throw new IllegalArgumentException("不能删除空的队列");
        }
        E ret = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size--;
        if(size == getCapacity()/4 && getCapacity() /2 != 0){
            resize(getCapacity()/2);
        }
        return ret;
    }
    //获取循环队列的队首
    @Override
    public E getFront() {
        if(isEmpty()){
            throw new IllegalArgumentException("队列为空");
        }
        return data[front];
    }
    //扩容
    private void resize(int newCapacity){
        E[] newData = (E[]) new Object[newCapacity + 1];
        for (int i = 0; i < size; i++) {
            newData[i] = data[(front + i) % data.length];
        }
        data = newData;
        front = 0;
        tail = size;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: size = %d , capacity = %d\n",size,getCapacity()));
        res.append("front [");
        for (int i = front; i != tail; i = (i + 1) % data.length) {
            res.append(data[i]);
            if((i + 1) % data.length != tail){
                res.append(",");
            }
        }
        res.append("] tail");
        return res.toString();
    }

    public static void main(String[] args) {
        LoopQueue<Integer> loopQueue = new LoopQueue<>();
        for (int i = 0; i < 11; i++) {
            loopQueue.enqueue(i);
            System.out.println(loopQueue);

            if(i % 3 == 2){
                loopQueue.dequeue();
                System.out.println(loopQueue);
            }
        }
    }
}

    4.LinkedListQueue.java

    /**
 * 用链表实现队列
 * @param <E>
 */
public class LinkedListQueue<E> implements Queue<E> {
    /**
     * 创建链表的内部类
     */
    private class  Node{
        public E e;
        public Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this(e,null);
        }

        public Node(){
            this(null,null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node head,tail; //指向队首和队尾
    private int size; //队列大小

     //初始化一个空的队列,链表没有头结点
    public LinkedListQueue() {
        head = null;
        tail  = null;
        size = 0;
    }

    //返回队列的大小
    @Override
    public int getSize() {
        return size;
    }

    //判断队列是否为空
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    //链表队列入队
    @Override
    public void enqueue(E e) {
        if(tail == null){
            tail = new Node(e);
            head = tail;
        }else {
            tail.next = new Node(e);
            tail = tail.next;
        }
        size++;
    }

    //链表队列出队
    @Override
    public E dequeue() {
        if(isEmpty()){
            throw new IllegalArgumentException("队列为空");
        }
        Node resNode = head;
        head = head.next;
        resNode.next = null;
        if(head == null){
            tail = null;
        }
        size--;
        return resNode.e;
    }

    //获得链表队列的首个元素
    @Override
    public E getFront() {
        if(isEmpty()){
            throw new IllegalArgumentException("队列为空");
        }
        return head.e;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Queue: ");
        Node cur = head;
        while (cur != null){
            res.append(cur + "->");
            cur = cur.next;
        }
        res.append("NULL");
        return res.toString();
    }
    public static void main(String[] args) {
        LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<>();
        for (int i = 1; i <= 10; i++) {
            linkedListQueue.enqueue(i);
            System.out.println(linkedListQueue);

            if(i % 3 ==2){
                linkedListQueue.dequeue();
                System.out.println(linkedListQueue);
            }
        }
    }
}

    微信公众号：


    点点关注，点关注，不迷路！

    相关文章

      网友评论

        本文标题：算法与数据结构系列之[队列]

        本文链接：https://www.haomeiwen.com/subject/iaojxctx.html

        延伸阅读

        深度阅读

        • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

        栏目导航

        热点阅读

        算法与数据结构

        关于我们|服务条款|联系我们|算法与数据结构系列之[队列]|投稿指南|网站地图|RSS订阅|排版工具|手机版

        提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

        Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

        备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

        本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

        所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！