数据结构实验报告——队列

• 实验目的与要求
• 实验步骤与内容
• 问题与说明
• 备注
• 程序清单

实验目的与要求

1.理解队列的表示方式

2.实现队列的各项功能

3.使用顺序和链式实现队列

4.双向队列

实验步骤与内容

队列（Queue）是遵循“FIFO”即“先进先出”规则，队首为front，队尾rear。下面给出队列的ADT

ADT Queue{
    数据对象:D={ai|ai∈ElemSet, i=1,2,3...,n, n≥0}
    数据关系:R={<ai-1,ai>|ai-1,ai∈D, i=2,3,...,n}
    约定a1为队首，an为队尾
    基本操作: CreattQue(),EmptyQue(),InsertQue(),DeleteQue()
}ADT Queue

队列的顺序表示及实现

#define MAX_QUEUE_SIZE 100
typedef struct queue{
    ElemType Queue_array[MAX_QUEUE_SIZE];
    int front;
    int rear;
}SqQueue;

先加元素再加指针
先进：rear=rear+1

先出：front=front+1

初始化：front=rear=0（可以初始化为-1，充分利用空间）；

入队：插入rear，rear+1；

出队：删去front，front++；

队空front==rear；

队满：rear=MAXQUEUESIZE-1；

循环队列

将队列看成一个首尾相接的圆环，并称为循环队列(Circular Queue)当队首队尾指向上界时，加1操作如果是指向向量的下界。i=(i+1)%MAX_QUEUE_SIZE。

队列的链式存储结构

1.队列的链式存储表示

队列的链式存储结构简称为链队列，它是限制仅在表头进行删除操作和表尾进行插入操作的单链表。

队列有两类不同的节点，数据元素节点，队列的队首指针和队尾指针。

数据元素节点类型定义

typedef struct Qnode {
    ElemType data;
    struct Qnode *next;
}Qnode;

指针节点类型定义

typedef struct link_queue{
    Qnode *front,*rear;
}

2.链队操作

链队列的初始化

LinkQueue *Init_Queue(void){
    LinkQueue *Q;
    Qnode *p;
    Q=(LinkQueue *)malloc(sizeof(LinkQueue));
    p=(Qnode *)malloc(sizeof(Qnode));
    p->next=NULL;
    Q.front=Q.rear=p;
    return Q;
}

入队（尾插）

Status Insert_Queue(LinkQueue *Q,ElemType e){
    Qnode *p;
    p=(Qnode *)malloc(sizeof(Qnode));
    p->data=e;
    p->next=NULL;
    Q.rear->next=p;
    Q.rear=p;
    return OK;
}

出队（头删除）

Status Delete_LinkQueue(LnikQueue *Q,ElemType *e){
    if(Q.frornt==Q.rear) return ERROR;
    p=Q.front->next;
    *e=p->data;
    Q.front->next=p->next;
    if(p==Q.rear) Q.rear=Q.front;
    free(q);
    return OK;
}

销毁队列

Status DestoryQueue(LinkQueue *Q){
    while(Q.front!=NULL){
        Q.rear=Q.front->next;
        free(Q.fornt);
        Q.front=Q.rear;
    }
    return OK;
}

双端队列

可以双端进行插入删除操作

问题与说明

CLion，IDEA

备注

程序清单

Deque Java实现

import java.util.Iterator;
import java.lang.*;
import java.util.NoSuchElementException;
import java.lang.IllegalArgumentException;
import java.lang.UnsupportedOperationException;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdIn;

public class Deque implements Iterable {
    private Node first;
    private Node last;
    private int n;

    private class Node {
        private Node next;
        private Item item;
        private Node front;
    }

    public Deque() {
        first = null;
        last = null;
        n = 0;
    } // construct an empty deque

    public boolean isEmpty() {
        return n == 0;
    }  // is the deque empty?

    public int size() {
        return n;
    }     // return the number of items on the deque

    public void addFirst(Item item) {
        if (item == null) throw new IllegalArgumentException();
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        if (isEmpty()) last = first;
        else {
            oldfirst.front = first;
            first.next = oldfirst;
        }
        n++;
    }  // add the item to the front

    public void addLast(Item item) {
        if (item == null) throw new IllegalArgumentException();
        Node oldlast = last;
        last = new Node();
        last.item = item;
        if (isEmpty()) first = last;
        else {
            oldlast.next = last;
            last.front = oldlast;
        }
        n++;
        }   // add the item to the end

    public Item removeFirst() {
        if (isEmpty()) throw new NoSuchElementException();
        Item item = first.item;
        first=first.next;
        n--;
        if(isEmpty()) last=null;
        else first.front = null;
        return item;
    }   // remove and return the item from the front

    public Item removeLast() {
        if (isEmpty()) throw new NoSuchElementException();
        Item item = last.item;
        last = last.front;
        n--;
        if(isEmpty()) first =null;
        else last.next = null;
        return item;

    } // remove and return the item from the end

    public Iterator iterator() {
        return new ListIterator(first);
    } // return an iterator over items in order from front to end

    private class ListIterator implements Iterator {
        private Node current;
        public ListIterator(Node first) {
            current = first;
        }

        public boolean hasNext() {
            return current != null;
        }

        public void remove() {
            throw new UnsupportedOperationException();
            /*Not Supported*/
        }

        public Item next() {
            if(!hasNext()) throw new java.util.NoSuchElementException();
            Item item = current.item;
            current = current.next;
            return item;
        }
    }

    public static void main(String[] args) {
        Deque deque = new Deque ();
        while(!StdIn.isEmpty()) {
            String s = StdIn.readString();
            if(!s.equals("-")) {
                StdOut.println("1->deque.size()=" +deque.size());
                deque.addFirst(s);
                StdOut.println("2->deque.size()=" +deque.size());
            }
            else if(!deque.isEmpty()) {
                StdOut.println(deque.removeFirst() + " ");
                StdOut.println("3->deque.size()=" +deque.size());
            }
        }
        StdOut.println("(" + deque.size() +" left on the deque)");
    }
}