精华内容
下载资源
问答
  • 2021-04-20 22:45:11

    队列

    顺序实现

    #define MaxSize 10
    typedef struct{
        ElemType data[MaxSize];//静态数组存放队列元素
        int front,rear;//队头和队尾指针
    }SqQueue;
    

    循环队列——入队

    bool EnQueue(SqQueue &Q,ElemType x){
        if((Q.rear+1)%MaxSize==Q.front){//队满
            return false;
        }
        Q.data[Q.rear]=x;
        Q.rear=(Q.rear+1)%MaxSize;//队尾指针加1取模
        return true;
    }
    

    循环队列——出队

    bool DeQueue(SqQueue &Q,ElemType &x){
        if(Q.rear==Q.front)
            return false;
        x=Q.data[Q.front];
        Q.front=(Q.front+1)%MaxSize;
        return true;
    }
    

    循环队列处理队满的方法

    a.牺牲一个存储空间

    1. 队空:Q.front==Q.rear
    2. 队满:(Q.rear+1)%MaxSize==Q.rear
    3. 队列中的元素个数:(Q.rear-Q.front+MaxSize)%MaxSize

    b.队列类型中增设一个表示数据元素个数的数据成员

    #define MaxSize 10
    typedef struct{
        ElemType data[MaxSize];//静态数组存放队列元素
        int front,rear;//队头和队尾指针
        int Size;//当前队列中元素个数
    }SqQueue;
    

    c.队列类型中增设标签tag

    1. 删除操作时,tag=0,若Q.rear==Q.front,则队为空
    2. 入队操作时,tag=1,若Q.rear==Q.front,则队为满

    队列链式实现

    定义

    front指向头结点head

    rear指向最后一个结点

    typedef struct LinkNode{//链式队列结点
        ElemType data;
        srtuct LinkNode *next;
    }LinkNode;
    
    typedef struct{//链队列
        LinkNode *front,*rear;//队列的队头和队尾指针
    }LinkQueue;
    

    初始化

    //带头结点的初始化链队列
    void InitQueue(LinkQueue &Q){
        //初始时,front,rear 都指向头结点
        Q.front=Q.rear=(LinkNode *)malloc(sizeof(LinkNode));
        Q.front->next=NULL;
    }
    

    入队

    void EnQueue(LinkQueue &Q,ElemType x){
        LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
        s->data=x;
        s->next=NULL;
        Q.rear->next=s;
        Q.rear=s;
    }
    

    出队

    bool DeQueue(LinkQueue &Q,ElemType &x){
        if(Q.front==Q.rear){
            return false;
        }
        LinkNode *p=Q.front->next;
        x=p->data;
        Q.front->next=p->next;
        if(Q.rear==p){
            Q.rear=Q.front;
        }
        free(p);
        return true;
    }
    

    双端队列

    1. 两端插入和删除
    2. 输入受限的双端队列:只允许一端插入,两端删除的线性表
    3. 输出受限的双端队列:只允许从两端插入,一端删除的线性表

    队列的应用

    1. 树的层次遍历(父节点先入队,然后将父节点的子结点入队,父节点出队;然后依次对队列中的元素进行上述操作)
    2. 图的广度优先遍历
    3. 操作系统的资源分配
    4. 数据缓冲区
    更多相关内容
  • 双端队列可以在队列任意一端入队和出队。 操作 Deque() 创建个空的双端队列 add_front(item) 从头加入个item元素 add_rear(item) 从队尾加入个item元素 remove_front() 从头删除个item元素 remove_rear...
  • 掌握了栈与队列后,如何将二者的优势联系起来。这里简单的写了Java代码了解双端队列

    写在前面的话:

    1.熟悉栈、队列相关知识

    2.熟悉数组的中间插入

    3.熟悉数组如何扩容


    目录

    1.双端队列

     2.测试双端队列


     

    项目结构:(双端队列同样属于栈&队列范畴)

     

     

    1.双端队列

    Deque.java
    /*
        双端队列:[拓展知识]
    
        简单的介绍:
            1.为了充分利用数组空间,特此采用循环队列
            2.本程序考察了参数的应用、数组的中间插入和超范围插入(扩容)
            3.存储方式可以用数组外,还可以采用链表(本程序当中未涉及)
    
        技巧:
            1.熟悉栈与队列,之后无障碍阅读
            2.熟悉数组的中间插入
            3.熟悉数组如何进行扩容
     */
    
    public class Deque {
    
        private int[] array;
        private int font;//双端队列也是队列!同样有队头
        private int rear;
        int size;//元素个数
    
        public Deque(){
            array = new int[10];
        }
    
        //指定长度的队列
        public Deque(int capacity){
            array = new int[capacity];
        }
    
        /**
         * 入队
         * @param element 插入的元素
         * @param front_or_behind 从后面插入元素(参数填入:behind)还是前面插入元素(参数填入:front)
         */
        public void enDeque(int element,String front_or_behind){
    
            //不管是在前面插入或者后面插入,当队列为空时,插入元素只有1种可能
            if(size == 0){
                array[0] = element;
                rear += (rear + 1)%array.length;
                size++;
                return;//插入完毕,直接返回
            }
    
            //判断插入顺序
            if(front_or_behind == "front"){
                //判断队列是否已满
                if(size >= array.length - 1){//元素个数大于或等于数组长度(要留一个,故减一)
                    //进行扩容
                    expandCapacity();
                }
                //队列未满可进行插入
                insert(font,element);//在队头插入数据
            }else if(front_or_behind == "behind"){
                //判断队列是否已满
                if(size >= array.length - 1){//元素个数大于或等于数组长度(要留一个空,故减一)
                    //进行扩容
                    expandCapacity();
                }
                //队列未满可进行插入
                array[rear] = element;
                rear = (rear + 1)%array.length;
                size++;//元素个数加1
            }else{
                //输入有误
                throw new IllegalArgumentException("输入参数有误!非front或behind!");
            }
        }
    
        /**
         * 出队
         * @param front_or_behind 从后面删除元素(参数填入:behind)还是前面删除元素(参数填入:front
         */
        public void outDeque(String front_or_behind) throws Exception{
    
            //判断队列是否为空
            if(size == 0){
                throw new Exception("队列为空,无法获取数据");
            }
    
            if(front_or_behind == "front"){
                font = (font + 1)%array.length;
                size--;//元素个数减一
            }else if(front_or_behind == "behind"){
                rear--;
                if(rear <= -1){
                    rear = array.length - 1;
                }
                size--;//元素个数减一
            }else{
                throw new IllegalArgumentException("输入参数有误!非front或behind!");
            }
        }
    
        public void expandCapacity(){
    
            int[] newArray = new int[array.length * 2];
    
            if(newArray.length > 100){
                throw new IllegalArgumentException("不准栈的深度超过100");
            }
    
            //将原数组复制到新数组里
            for(int i = font,n = 0;n < size;i = (i + 1)%array.length){
                newArray[n++] = array[i];
            }
    
            //扩大后,队头队尾发生变化
            font = 0;
            rear = size;
    
            array = newArray;
        }
    
        /**
         * 数组的中间插入、超范围插入(扩容)
         * @param index    插入的位置
         * @param element  插入的元素
         */
        public void insert(int index , int element){
    
            //在这里不需要判断是否需要扩容,在调用该方法前已经判断了
    
            //判断index是否超出数组范围
            if(index < 0 || index > array.length){//还不完善,有能力可以进一步修改
                throw new IllegalArgumentException("参数index不符合范围!参数index的值:" + index);
            }
    
            //在数组下标index以及之后的元素依次往后移动(记住:这里是循环队列!如:array[array.length] == array[0])
            //
            //    在这里分两种情况:
            //        1.rear后面没有接元素:这种比较简单,元素依次往后移一位【常规写法】
            //        2.rear后面有元素(队尾在中间):这种比较麻烦,关键在于后面有个元素是队头
            //
            if(rear >= font){
                //这种情况说明:常规情况,[1,font,...,2,3,4,rear]
                for(int i = rear - 1;i >= index;i--){
                    array[i + 1] = array[i];//往后移
                }
            }else{
                //这种情况说明:[1,2,rear,...,3,4,font,...]
                for(int i = rear - 1;i != index;i--){
                    if(i <= -1){
                        i = array.length - 1;
                        array[0] = array[i];
                        continue;
                    }
                    array[i + 1] = array[i];
                }
                array[(index + 1)%array.length] = array[index];//将队头向后移
            }
    
            //将元素插入数组下标index处  ==> 数组更新操作
            array[index] = element;
    
            //插入后,元素个数增加,队尾加1
            size++;
            rear = (rear + 1)%array.length;
        }
    
        @Override
        public String toString() {
            String str = "[";
            //只遍历数组当中的元素个数
            //   分两种情况:
            //      1. rear >= font [1,font,...,2,3,4,rear]
            //      2. rear < font  [1,2,rear,...,3,4,font,...]
            if(rear >= font){
                //常规解法,依次遍历即可
                for(int i = font;i < rear;i = (i + 1)%array.length){
                    str += array[i];
                    //当不是最后1个元素,需要加逗号
                    if(i != rear - 1){
                        str += ",";
                    }
                }
            }else{
                //rear < font情况
                for(int i = font;i < size;i = (i + 1)%array.length){
                    str += array[i];
                    //当不是最后1个元素,需要加逗号
                    if(i != rear - 1){
                        str += ",";
                    }
                }
            }
    
            //最后加一个"]"结尾
            str += "]";
            return str;
        }
    }

     2.测试双端队列

    TestArray.java
    public class TestArray {
    
        public static void main(String[] args) {
    
            Deque deque = new Deque(3);
    
            System.out.println("入队:");
    
            deque.enDeque(1,"behind");
            deque.enDeque(2,"behind");
            deque.enDeque(3,"front");
            deque.enDeque(4,"front");
            deque.enDeque(5,"behind");
            deque.enDeque(6,"behind");
            deque.enDeque(7,"front");
    
            System.out.println(deque);
    
            System.out.println("出队:");
    
            try {
                deque.outDeque("front");
                deque.outDeque("behind");
                deque.outDeque("front");
                deque.outDeque("front");
            } catch (Exception e) {
                e.printStackTrace();
            }
    
            System.out.println(deque);
    
            System.out.println("入队:");
            deque.enDeque(-1,"front");
            deque.enDeque(6,"behind");
            deque.enDeque(-4,"front");
            deque.enDeque(-5,"behind");
    
            System.out.println(deque);
    
            System.out.println("出队:");
    
            try {
                deque.outDeque("front");
                deque.outDeque("behind");
                deque.outDeque("front");
                deque.outDeque("front");
            } catch (Exception e) {
                e.printStackTrace();
            }
    
            System.out.println(deque);
        }
    }

    完 

     

    展开全文
  • 队列文档之双端队列

    2022-05-09 22:40:32
    双端队列是普通队列的扩展,是指允许端都可以进行入队和出队操作的队列(即可以在头进行入队和出队操作,也可以在队尾进行入队和出队操作的队列)。

    双端队列

    定义

    概念

    双端队列是普通队列的扩展,是指允许两端都可以进行入队和出队操作的队列(即可以在队头进行入队和出队操作,也可以在队尾进行入队和出队操作的队列)。其元素的逻辑结构仍然是线性结构,可以采用顺序存储,也可以采用链式存储。将队列的两端分别称为前端和后端,两端都可以入队和出队。

    在这里插入图片描述

    在双端队列入队时,前端进的元素排列在队列中后端进的元素的前面,后端进的元素排列在队列中前端进的元素的后面。在双端队列出队时,无论是前端还是后端出队,先出的元素排列在后出的元素的前面。

    除了上面的双端队列之外,还有两类受限的双端队列:

    • 输出受限的双端队列:允许在一端进行插入和删除,但在另一端只允许插入的双端队列称为输出受限的双端队列。

    在这里插入图片描述

    • 输入受限的双端队列:允许在一端进行插入和删除,但在另一端只允许删除的双端队列称为输入受限的双端队列。若限定双端队列从某个端点插入的元素只能从该端点删除,则该双端队列就变成了两个栈底相邻接的栈。

    在这里插入图片描述

    双端队列既可以采用顺序存储,也可以采用链式存储实现。下面所讲的是顺序存储实现,但也提供了链式存储实现代码。

    结构体

    /**
     * 双端队列结构体定义,跟循环队列的一样,只是 rear 在双端队列中名为 back
     */
    typedef struct {
        /**
         * 数据域,存储循环队列中的数据
         */
        int data[MAXSIZE];
        /**
         * 指针域,存储循环队列中队头元素的位置
         */
        int front;
        /**
         * 指针域,存储循环队列中队尾元素的位置
         */
        int back;
    } DoubleEndedQueue;
    

    特点

    • 输入受限的双端队列是指只能从队列一端输入,可以从两端输出的队列。
    • 输出受限的双端队列是指只能从队列一端输出,可以从两端输出的队列。
    • 如果双端队列允许从一端输入,从另一端输出,就是普通的队列;如果双端队列只允许从一端输入和输出,就是普通的栈。因此双端队列同时具有队列和栈两种数据结构的性质。

    基本操作

    注,完整代码请参考:

    一些注意事项:

    • DoubleEndedQueue 表示顺序存储的双端队列;LinkedDoubleEnedQueue 表示链式存储的双端队列。
    • 其中顺序存储的双端队列中底层是使用的循环队列,为了能够充分分配的空间。
    • 双端队列的结构体中的指针域虽然名字是 frontback,但是仍然表示队头指针和队尾指针,而队头指针也仍然指向队头元素,队尾指针指向队尾元素的下一位置。
    • DoubleEnedQueue 实现的双端队列大部分代码与循环队列的一致,关于循环队列请参考:文档-循环队列
    • 关于有些图中是 queuedeque 这个不重要,是画图时忘了修改,它们都表示队列,勿要关注。

    概述

    双端队列的常见操作如下:

    • void init(DoubleEndedQueue *deque):初始化双端队列。其中 deque 表示双端队列。
    • int isEmpty(DoubleEndedQueue deque):判断双端队列是否为空。其中 deque 表示双端队列。如果双端队列为空则返回 1,否则返回 0 表示非空。
    • int isFull(DoubleEndedQueue deque):判断双端队列是否已满。其中 deque 表示双端队列。如果双端队列已满则返回 1,否则返回 0。
    • int pushFront(DoubleEndedQueue *deque, int ele):从队头将元素入队。其中 deque 表示双端队列;ele 表示待入队的元素。如果队已满则不能入队,返回 0 表示入队失败;否则如果入队成功则返回 1。
    • int pushBack(DoubleEndedQueue *deque, int ele):从队尾将元素入队。其中 deque 表示双端队列;ele 表示待入队的元素。如果队已满则不能入队,返回 0 表示入队失败;否则如果入队成功则返回 1。
    • int popFront(DoubleEndedQueue *deque, int *ele):从队头将元素出队。其中 deque 表示双端队列;ele 用来保存出队元素。如果队空则不能出队,返回 0 表示出队失败;否则如果出队成功则返回 1。
    • int popBack(DoubleEndedQueue *deque, int *ele):从队尾将元素出队。其中 deque 表示双端队列;ele 用来保存出队元素。如果队空则不能出队,返回 0 表示出队失败;否则如果出队成功则返回 1。
    • int size(DoubleEndedQueue deque):获取双端队列中的元素个数。其中 deque 表示双端队列。返回双端队列中的元素个数。
    • int getFront(DoubleEndedQueue deque, int *ele):获取双端队列中的队头元素。其中 deque 表示双端队列;ele 用来保存队头元素。如果队空则不能获取到队头元素,返回 0 表示获取失败;如果获取成功则返回 1。
    • int getBack(DoubleEndedQueue deque, int *ele):获取双端队列中的队尾元素。其中 deque 表示双端队列;ele 用来保存队尾元素。如果队空则不能获取到队尾元素,返回 0 表示获取失败;如果获取成功则返回 1。
    • void clear(DoubleEndedQueue *deque):清空双端队列。其中 deque 表示双端队列。
    • void print(DoubleEndedQueue deque):打印双端队列所有元素。其中 deque 表示双端队列。

    init

    初始化双端队列。

    在这里插入图片描述

    实现步骤:

    • 将队头指针 front 和队尾指针 back 都指向 0,表示空队列。

    实现代码如下:

    /**
     * 初始化双端队列
     * @param deque 待初始化的双端队列
     */
    void init(DoubleEndedQueue *deque) {
        // 双端队列初始时,队头指针和队尾指针仍然都指向 0,表示是空队列
        deque->front = 0;
        deque->back = 0;
    }
    

    isEmpty

    判断双端队列是否为空。如果为空则返回 1,否则返回 0 表示非空。

    在这里插入图片描述

    实现步骤:

    • 判断队头指针 front 和队尾指针 back 是否指向同一位置,即 deque.front==deque.back

    实现代码如下:

    /**
     * 判断双端队列释放为空
     * @param deque 双端队列
     * @return 如果双端队列为空则返回 1,否则返回 0 表示非空
     */
    int isEmpty(DoubleEndedQueue deque) {
        // 只要队头指针和队尾指针相等,那么表示双端队列为空,无论指针在哪个位置
        if (deque.front == deque.back) {
            return 1;
        } else {
            return 0;
        }
    }
    

    isFull

    判断双端队列是否已经满队。如果已满则返回 1,否则返回 0 表示未满。

    在这里插入图片描述

    实现步骤:

    • 如果满足条件 (queue.back+1)%MAXSIZE==queue.front,那么就认为队满。

    实现代码如下:

    /**
     * 判断双端队列是否已满
     * @param queue 双端队列
     * @return 如果双端队列已满则返回 1,否则返回 0 表示队列非满
     */
    int isFull(DoubleEndedQueue deque) {
        // 判断条件跟循环队列一样,因为底层就是循环队列
        if ((deque.back + 1) % MAXSIZE == deque.front) {
            return 1;
        } else {
            return 0;
        }
    }
    

    pushFront

    将元素从队头入队。如果队未满才能入队,否则返回 0 表示入队失败。如果入队成功则返回 1。以 deque=[a, b, c]; ele=x 为例如图所示:

    在这里插入图片描述

    实现步骤:

    • 参数校验,如果队满则不能入队。返回 0 表示入队失败。
    • 先移动队头指针,将队头指针减一,但不是单纯的减一。因为队头指针始终指向队头元素,所以如果要从队头入队,那么队头指针要先指向一个可以存放元素的位置,只能向前移动,所以要减一。但是是循环队列,不能单纯的减一,如果 front==0 那么减一就会变成 -1,而下标没有 -1,所以要移动到数组的倒数第一个位置,即 MAXSIZE-,通过对 MAXSIZE 取余就会实现这种自动转换。
    • 接着进行赋值,将队头指针所指向的位置赋予 ele 值。使得队头指针始终指向队头元素。
    • 返回 1 表示入队成功。

    实现代码如下:

    /**
     * 从队头将元素入队
     * @param queue 双端队列
     * @param ele 待入队的元素
     * @return 如果队列已满则不能入队返回 0 表示入队失败;否则返回 1 表示入队成功
     */
    int pushFront(DoubleEndedQueue *deque, int ele) {
        // 0.参数校验,如果队满则不能入队
        if (isFull(*deque)) {
            return 0;
        }
    
        // 1.将元素插入到队列的头部
        // 1.1 由于队头指针指向队列的队头元素,所以先修改队头指针。新元素应该插入到原队头元素的前面,所以要队头指针减一,因为是循环队列,所以要对 MAXSIZE 取余
        deque->front = (deque->front - 1 + MAXSIZE) % MAXSIZE;
        // 1.2 再对队头指针所指向的位置进行赋值
        deque->data[deque->front] = ele;
        // 1.3 返回 1 表示入队成功
        return 1;
    }
    

    pushBack

    从队尾将元素入队。如果队未满才能入队,否则返回 0 表示入队失败。如果入队成功则返回 1。普通队列就是从队尾入队的,所以下面的图以及代码同循环队列的 enQueue 方法是一致的。以 deque=[a, b, c]; ele=x 为例如图:

    在这里插入图片描述

    实现步骤:

    • 参数校验,如果队满则不能入队。返回 0 表示入队失败。
    • 先进行赋值,将队尾指针所指向的位置赋予 ele 值。
    • 接着队尾指针加一,指向队尾元素的下一个位置。保证队尾指针始终指向队尾元素的下一位置。
    • 返回 1 表示入队成功。

    实现代码如下:

    /**
     * 从队尾将元素入队
     * @param queue 双端队列
     * @param ele 待入队的元素
     * @return 如果队列已满则不能入队返回 0 表示入队失败;否则返回 1 表示入队成功
     */
    int pushBack(DoubleEndedQueue *deque, int ele) {
        // 0.参数校验,如果队满则不能入队
        if (isFull(*deque)) {
            return 0;
        }
    
        // 1.将元素插入到队列的尾部
        // 1.1 由于队尾指针指向队尾元素的下一个位置,所以直接赋值即可
        deque->data[deque->back] = ele;
        // 1.2 插入元素后,需要移动队尾指针,将其加一,指向队尾元素的下一个位置,因为是循环队列,所以要对 MAXSIZE 取余
        deque->back = (deque->back + 1) % MAXSIZE;
        // 1.3 返回 1 表示入队成功
        return 1;
    }
    

    popFront

    将元素从队头出队。如果队空则不能出队,返回 0 表示出队失败;将出队元素保存到 ele,并返回 1 表示出队成功。普通队列就是从队头出队的,所以下面的图以及代码同循环队列的 deQueue 方法是一致的。以 deque=[a, b, c, d, e, f, g] 为例如图所示:

    在这里插入图片描述

    实现步骤:

    • 参数校验,如果队空,则不能出队。返回 0 表示出队失败。
    • 将元素出队。用 ele 保存队头指针所指向的元素。
    • 然后将队头指针加一,保证队头指针始终指向队头元素。
    • 返回 1 表示出队成功。

    实现代码如下:

    /**
     * 从队头将元素出队
     * @param deque 双端队列
     * @param ele 用来保存出队元素
     * @return 如果队空则返回 0 表示出队失败,否则返回 1 表示出队成功
     */
    int popFront(DoubleEndedQueue *deque, int *ele) {
        // 0.参数校验,如果队空则不能出队
        if (isEmpty(*deque)) {
            return 0;
        }
    
        // 1.将队头元素出队
        // 1.1 用 ele 保存队头指针所指向的元素,即队头元素
        *ele = deque->data[deque->front];
        // 1.2 修改队头指针,将其加一,表示删除队头元素。因为是循环队列,所以要对 MAXSIZE 取余
        deque->front = (deque->front + 1) % MAXSIZE;
        // 1.3 返回 1 表示出队成功
        return 1;
    }
    

    popBack

    从队尾将元素出队。如果队空则不能出队,返回 0 表示出队失败;将出队元素保存到 ele,并返回 1 表示出队成功。以 deque=[a, b, c, d, e, f, g] 为例如图所示:

    在这里插入图片描述

    实现步骤:

    • 参数校验,如果队空,则不能出队。返回 0 表示出队失败。
    • 移动指针,先将队尾指针减一。由于队尾指针始终指向队尾元素的下一个位置,所以如果要获取到队尾元素,必须让队尾指针减一。但由于是循环队列,所以要对 MAXSIZE 取余。
    • 将元素出队,取出队尾指针所指向的值。此时队尾指针所指向的值在出队后就是无效的元素了,因为队尾指针仍然要保持指向队尾元素的下一个位置。
    • 返回 1 表示出队成功。

    实现代码如下:

    /**
     * 从队尾将元素出队
     * @param deque 双端队列
     * @param ele 用来保存出队元素
     * @return 如果队空则返回 0 表示出队失败,否则返回 1 表示出队成功
     */
    int popBack(DoubleEndedQueue *deque, int *ele) {
        // 0.参数校验,如果队空则不能出队
        if (isEmpty(*deque)) {
            return 0;
        }
        // 1.从队尾将元素出队
        // 1.1 由于队尾指针指向队尾元素的下一个位置,所以先修改队尾指针,将其减一,但由于是循环队列,所以要对 MAXSIZE 取余
        deque->back = (deque->back - 1 + MAXSIZE) % MAXSIZE;
        // 1.2 然后取出当前队尾指针所指向的元素,就是待出队的元素
        *ele = deque->data[deque->back];
        // 1.3 返回 1 表示出队成功
        return 1;
    }
    

    size

    获取双端队列中实际的元素个数。实际上就是获取循环队列的元素个数。

    在这里插入图片描述

    实现步骤:

    • 循环队列的元素个数即 (back-front+MAXSIZE)%MAXISZE

    实现代码如下:

    /**
     * 获取双端队列中的元素个数
     * @param deque 双端队列
     * @return 队列中的元素个数
     */
    int size(DoubleEndedQueue deque) {
        // 如果是顺序队列,则元素个数是 rear-front
        // 如果是循环队列,则元素个数是 (rear-front+MAXSIZE)%MAXSIZE
        return (deque.back - deque.front + MAXSIZE) % MAXSIZE;
    }
    

    getFront

    读取队头元素,但并不出队。如果队空则不能读取,则返回 0,否则用 ele 保存队头元素,返回 1 表示读取成功。

    在这里插入图片描述

    实现步骤:

    • 参数校验,如果队空则没有队头元素,自然也无法获取。返回 0 表示读取失败。
    • 直接读取队头指针所指向的元素。因为队头指针始终指向队头元素。

    实现代码如下:

    /**
     * 获取双端队列的队头元素
     * @param deque 双端队列
     * @param ele 用来保存队头元素
     * @return 如果出队成功则返回 1,否则返回 0 表示出队失败
     */
    int getFront(DoubleEndedQueue deque, int *ele) {
        // 0.参数校验,如果队列为空则不能获取队头元素
        if (isEmpty(deque)) {
            return 0;
        }
        // 1.用 ele 保存队头指针所指向的元素
        *ele = deque.data[deque.front];
        return 1;
    }
    

    getBack

    读取双端队列的队尾元素。如果双端队空为空则返回 0 表示读取失败。否则用 ele 保存队尾元素,并返回 1 读取成功。
    在这里插入图片描述

    实现步骤:

    • 参数校验,如果队空,则不能读取队尾元素。返回 0 表示读取失败。
    • 读取队尾指针所指向位置的前一个位置的元素,用 ele 保存。因为队尾指针始终指向队尾元素的下一个位置,所以要读取队尾元素,需要读取到队尾指针的前一个位置的元素。但并不是队尾指针单纯的减一,因为是循环队列。
    • 返回 1 表示读取成功。

    实现代码如下:

    /**
     * 获取双端队列的队尾元素
     * @param deque 双端队列
     * @param ele 用来保存队尾元素
     * @return 如果出队成功则返回 1,否则返回 0 表示出队失败
     */
    int getBack(DoubleEndedQueue deque, int *ele) {
        // 0.参数校验,如果队列为空则不能获取队尾元素
        if (isEmpty(deque)) {
            return 0;
        }
        // 1.用 ele 保存队尾指针所指向的前一个元素,因为队尾指针指向队尾元素的下一个位置,所以要减一,因为是循环队列,所以要对 MAXSIZE 取余
        *ele = deque.data[(deque.back - 1 + MAXSIZE) % MAXSIZE];
        return 1;
    }
    

    clear

    清空双端队列。实际上是清空循环队列。

    在这里插入图片描述

    实现步骤:

    • 将双端队列的队头指针 front 和队尾指针 back 都指向 0,表示空队列。但实际上队列中原有的元素仍然存在,并没有被重置为某个值。

    实现代码如下:

    /**
     * 清空双端队列
     * @param deque 双端队列
     */
    void clear(DoubleEndedQueue *deque) {
        // 即将队头指针和队尾指针指向 0,表示空队列
        deque->front = 0;
        deque->back = 0;
    }
    

    print

    打印双端队列中的所有有效元素。

    在这里插入图片描述

    实现步骤:

    • 从队头指针开始扫描整个双端队列,直到队尾指针结束,但不包括队尾指针所指向的元素。

    实现代码如下:

    /**
     * 打印双端队列从队头到队尾的所有元素
     * @param deque 双端队列
     */
    void print(DoubleEndedQueue deque) {
        printf("[");
        int front = deque.front;
        while (front != deque.back) {
            printf("%d", deque.data[front]);
            if (front != (deque.back - 1 + MAXSIZE) % MAXSIZE) {
                printf(", ");
            }
            front = (front + 1) % MAXSIZE;
        }
        printf("]\n");
    }
    

    注意事项

    无。

    练习题

    展开全文
  • 双端队列出队顺序图_双端队列

    千次阅读 2020-07-27 13:09:21
    双端队列出队顺序图 双端队列 (Double Ended Queue) Double ended queue is a more generalized form of queue data structure which allows insertion and removal of elements from both the ends, i.e , front...

    双端队列的出队顺序图

    Double ended queue is a more generalized form of queue data structure which allows insertion and removal of elements from both the ends, i.e , front and back.

    双头队列是队列数据结构的一种更通用的形式,它允许从两端(即正面和背面)插入和删除元素。

    Double Ended Queue

    双头队列的实现 (Implementation of Double ended Queue)

    Here we will implement a double ended queue using a circular array. It will have the following methods:

    在这里,我们将使用循环数组实现双端队列。 它将具有以下方法:

    • push_back : inserts element at back

      push_back:在后面插入元素

    • push_front : inserts element at front

      push_front:在前面插入元素

    • pop_back : removes last element

      pop_back:删除最后一个元素

    • pop_front : removes first element

      pop_front:删除第一个元素

    • get_back : returns last element

      get_back:返回最后一个元素

    • get_front : returns first element

      get_front:返回第一个元素

    • empty : returns true if queue is empty

      空:如果队列为空,则返回true

    • full : returns true if queue is full

      full:如果队列已满,则返回true

    // Maximum size of array or Dequeue
    
    #define SIZE 5
    
    class Dequeue
    {
        //front and rear to store the head and tail pointers
        int  *arr;
        int front, rear;  
        
        public :
    
        Dequeue()
        {
        	//Create the array
            arr = new int[SIZE];
    
            //Initialize front and rear with -1
            front = -1;
            rear = -1;
        }
     
        // Operations on Deque
        void  push_front(int );
        void  push_back(int );
        void  pop_front();
        void  pop_back();
        int  get_front();
        int  get_back();
        bool  full();
        bool  empty();   
    };

    在前面插入元素 (Insert Elements at Front)

    First we check if the queue is full. If its not full we insert an element at front end by following the given conditions :

    首先,我们检查队列是否已满。 如果未满,我们按照给定条件在前端插入一个元素:

    • If the queue is empty then intialize front and rear to 0. Both will point to the first element.

      如果队列为空,则将前和后初始化为0。两者都将指向第一个元素。

    • Double Ended Queue


    • Else we decrement front and insert the element. Since we are using circular array, we have to keep in mind that if front is equal to 0 then instead of decreasing it by 1 we make it equal to SIZE-1.

      否则,我们递减front并插入元素。 由于我们使用的是圆形数组,因此必须记住,如果front等于0,那么与其将其减1而不是使其等于SIZE-1。

    Double Ended Queue
    void Dequeue :: push_front(int key)
    {
        if(full())
        {
            cout << "OVERFLOW\n";
        }
        else
        {
        	//If queue is empty
        	if(front == -1)
        		front = rear = 0;
    
        	//If front points to the first position element 
            else if(front == 0)
                front = SIZE-1;
            
            else
            	--front;
            
            arr[front] = key;
        }
    }

    在后面插入元素 (Insert Elements at back)

    Again we check if the queue is full. If its not full we insert an element at back by following the given conditions:

    再次,我们检查队列是否已满。 如果未满,我们按照给定条件在后面插入一个元素:

    • If the queue is empty then intialize front and rear to 0. Both will point to the first element.

      如果队列为空,则将前和后初始化为0。两者都将指向第一个元素。

    • Else we increment rear and insert the element. Since we are using circular array, we have to keep in mind that if rear is equal to SIZE-1 then instead of increasing it by 1 we make it equal to 0.

      否则,我们增加后方并插入元素。 由于我们使用的是圆形数组,因此必须记住,如果后方等于SIZE-1,那么与其将其增加1而不是使其等于0。

    Double Ended Queue
    void Dequeue :: push_back(int key)
    {
        if(full())
        {
            cout << "OVERFLOW\n";
        }
        else
        {
            //If queue is empty
        	   if(front == -1)
        		  front = rear = 0;
    
        	   //If rear points to the last element
            else if(rear == SIZE-1)
                rear = 0;
            
            else
            	++rear;
            
            arr[rear] = key;
        }    
    }

    删除第一个元素 (Delete First Element)

    In order to do this, we first check if the queue is empty. If its not then delete the front element by following the given conditions :

    为此,我们首先检查队列是否为空。 如果不是,则按照给定条件删除front元素:

    • If only one element is present we once again make front and rear equal to -1.

      如果仅存在一个元素,则我们再次使前后等于-1。

    • Else we increment front. But we have to keep in mind that if front is equal to SIZE-1 then instead of increasing it by 1 we make it equal to 0.

      否则,我们增加前面。 但是我们必须记住,如果front等于SIZE-1,那么与其将其增加1而不是使其等于0。

    Double Ended Queue
    void Dequeue :: pop_front()
    {
        if(empty())
        {
            cout << "UNDERFLOW\n";
        }
        else
        {
        	//If only one element is present
            if(front == rear)
            	front = rear = -1;
    
            //If front points to the last element 
            else if(front == SIZE-1)
            	front = 0;
    
            else
            	++front;		
        }
    }

    删除最后一个元素 (Delete Last Element)

    Inorder to do this, we again first check if the queue is empty. If its not then we delete the last element by following the given conditions :

    为此,我们再次首先检查队列是否为空。 如果不是,则按照给定条件删除最后一个元素:

    • If only one element is present we make front and rear equal to -1.

      如果仅存在一个元素,则使前后等于-1。

    • Else we decrement rear. But we have to keep in mind that if rear is equal to 0 then instead of decreasing it by 1 we make it equal to SIZE-1.

      否则我们减少后方。 但是我们必须记住,如果后方等于0,那么与其将其减1而不是使其等于SIZE-1。

    Double Ended Queue
    void Dequeue :: pop_back()
    {
        if(empty())
        {
            cout << "UNDERFLOW\n";
        }
        else
        {
        	//If only one element is present
            if(front == rear)
            	front = rear = -1;
    
            //If rear points to the first position element 
            else if(rear == 0)
            	rear = SIZE-1;
    
            else
            	--rear;		
        }
    }

    检查队列是否为空 (Check if Queue is empty)

    It can be simply checked by looking where front points to. If front is still intialized with -1, the queue is empty.

    只需查看前端指向的位置即可对其进行检查。 如果front仍使用-1初始化,则队列为空。

    bool Dequeue :: empty()
    {
        if(front == -1)
        	return true;
        else
        	return false;
    }

    检查队列是否已满 (Check if Queue is full)

    Since we are using circular array, we check for following conditions as shown in code to check if queue is full.

    由于我们使用的是循环数组,因此我们检查代码中所示的以下条件,以检查队列是否已满。

    bool Dequeue :: full()
    {
        if((front == 0 && rear == SIZE-1)  ||
        	(front == rear + 1))
            return true;
        else
            return false;
    }

    返回第一个元素 (Return First Element)

    If the queue is not empty then we simply return the value stored in the position which front points.

    如果队列不为空,那么我们只返回存储在前端位置的值。

    int Dequeue :: get_front()
    {
        if(empty())
        {	cout << "f=" <<front << endl;
            cout << "UNDERFLOW\n";
            return -1;
        }
        else
        {
            return arr[front];
        }
    }

    返回最后一个元素 (Return Last Element)

    If the queue is not empty then we simply return the value stored in the position which rear points.

    如果队列不为空,那么我们只返回存储在后面位置的值。

    int Dequeue :: get_back()
    {
        if(empty())
        {
            cout << "UNDERFLOW\n";
            return -1;
        }
        else
        {
            return arr[rear];
        }
    }

    翻译自: https://www.studytonight.com/data-structures/double-ended-queue

    双端队列的出队顺序图

    展开全文
  • 数据结构之双端队列

    2021-07-11 13:01:17
    文章目录前言双端队列模型二、双端队列的实现三、在前面插入元素四、在后面插入元素五、检查队列是否空六、检查队列是否已满总结 前言 双端队列个端部,首部尾部,并且项在集合中保持不变。 双端不同...
  • 第三章:栈队列上篇文章中我们讲了 学习数据结构--第三章:栈队列(栈的基本操作)下面讲解队列的基本操作、循环队列、双端队列1.队列的基本概念队列(Queue) 只允许在表的 一端(队尾) 进行插入,表的 另一端(对头) ...
  • 双端队列(数组表示)

    2009-05-10 10:35:00
    置空操作,队尾指针置   {   front = rear = 0;   }   bool IsEmpty () const   {   return ( front == rear ) ? true : false ;   }   bool IsFull () const...
  • 数据结构作业9复习

    千次阅读 2020-12-09 08:55:29
    7-1 银行业务队列简单模拟 (25分) ...输入为一行正整数,其中第1个数字N(≤1000)顾客总数,后面跟着N顾客的编号。编号奇数的顾客需要到A窗口办理业务,偶数的顾客则去B窗口。数字间以空格分隔。
  • 定义:个线性表的端当做栈底分别进行入栈出栈的操作,主要利用了栈"栈底位置不变,而栈顶位置动态变化"的特性。 我们把双端栈叫做ArrayDoubleEndStack,双端栈是线性表的种,更是栈的个特殊的分类,所以...
  • c++,队列基本操作
  • 队列种特殊的线性表,只能在头尾端进行操作队尾(rear):只能从队尾添加元素,一般叫做 enQueue,入队队头(front):只能从头移除元素,一般叫做 deQueue,出队先进先的原则,First In First Out,FIFO普通...
  • //双端队列的实现:队列左为端口1,队列右端口2 #include #include #include #define LEN sizeof(struct DQueuelist) using namespace std; typedef struct DQueuelist //定义结构体结点 { int data; //结构体...
  • 具有先进先的特点,双端队列是指“可以在首队尾都可以增删元素”的种数据结构 步骤:定义接口:Dequeue、Stack 定义个接口(Dequeue、Stack),然后让我们创建的ArrayDeque类实现这个接口。 Dequeue...
  • 循环双端队列和循环队列在实现上几乎是一样的,需要注意的有以下几点: 1、定义循环变量 front rear 。一直保持这个定义,到底是先赋值还是先移动指针就很容易想清楚了。 ① front:指向队列头部第 1 个有效数据...
  • #include<iostream> using namespace std; typedef struct node { int data; node* next;... node* front, * rear;... front = new node;... front->... rear = front; } void EnQueue() { cout &.
  • 双端队列定义 Deque接口 public interface Deque<E> extends Queue<E> { public void addFirst(E element); public void addLast(E element); public E removeFirst(); public E removeLast(); ...
  • 特殊的队列 --- 双端队列
  • 循环双端队列:可以进行端添加、删除操作的循环队列 队列底层也可以使用动态数组实现,并且各项接口也可以优化到O(1)的时间复杂度这个用数组实现优化之后的队列也叫做:循环队列。 上述图示: ①、front == tail...
  • 循环队列与双端队列

    2022-01-14 19:04:33
    很明显,入队的时间复杂度O(1),出队的时间复杂度O(n) 线性表增删数据元素时间复杂符都是O(n),但是这个是按平均算的 队列出队时间复杂度O(n),可不是按平均算的,因为每次出队都是O(n) 循环队列ArrayLoopQueue...
  • 队列: 简称,实质是种操作受限的线性表,其限制仅允许在表的一端进行插入,在表的另一端进行删除。可以插入的一端是队尾,可以删除的一端是... 使用数组模拟,个标记,个标记首,个标记...
  • 双端队列

    万次阅读 多人点赞 2019-06-22 21:35:54
    双端队列(deque,即double-ended queue的缩写)是种具有队列栈性质的数据结构,即可(也只能)在线性表的端进行插入删除。、 看到就直接蒙了,啥玩意??? 先看一下啥是队列: 队列是种特殊的...
  • 像栈一样,队列也是种线性表。它允许在表的一端插入数据,在另一端删除元素。插入元素的这一端称之队尾。删除元素的这一端我们称之为队首。 队列的特性: 1.在队尾插入元素,在首删除元素。 2.先进先...
  • 如果允许在循环队列端都可以进行插入删除操作,要求: - 写循环队列的类型定义。 - 分别从队尾删除头插入的算法。
  • Java双端队列的代码实现

    千次阅读 2021-06-11 14:42:51
    由于入队和出队操作时头尾指针只会增加不会减小,当rear指向到分配的连续空间之外时,队列无法再插入新元素,被删除元素的空间永远无法被重新利用,这种情况叫队列的“假上溢”现象,即头尾指针前的空间没有使用,...
  • python双端队列实现

    2021-12-31 11:20:08
    双端队列可以在队列任意一端入队和出队。 操作: Deque() 创建个空的双端队列 add_front(item) 从头加入个item元素 add_rear(item)从队尾加入个item元素 remove_front() 从头删除个item元素 remove_...
  • 双端队列思想解析

    2020-03-15 20:40:17
    双端队列中的元素可以从端弹,其限定插入删除操作在表的端进行。 能够看得懂吗?反正我是不能,但这确实是用很精炼的语言描述了双端队列的性质。这句话的内容蕴含这样的信息deque在具备队列的性质同时,...
  • LC641 设计循环双端队列 LC143 重排链表
  • Problem Description 中午买饭的人特多,食堂真是太拥挤了,买个饭费劲,理工大的小孩还是很聪明的,直接奔政通超市,哈哈,确实,政通...问题是这样的:开始有两队人在排队,现在咱们只研究第一队,现在我们给每个人个...
  • 定义 队列是只允许在一端进行插入,而在另一端进行删除的线性表。 头(Front):允许删除的一端,又称为首。 队尾(Rear): 允许插入的一端。 先进入队列的元素必然...用数组来实现队列,可以将首放在数组下...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,529
精华内容 611
关键字:

18.长度为8的一位数组构建双端队列,front和rear分别为0,4,两次出队,两次入队后,f

友情链接: Kalman_3.rar