精华内容
下载资源
问答
  • 循环队列顺序存储结构Java

    千次阅读 2019-12-19 16:33:54
    循环队列顺序存储结构 在上次,我们讲到的是,队列的顺序存储结构也是由ArrayList实现的,从此就可以看出,在入队时候的时间复杂度为O(1),但是在出队时候的时间复杂度为O(n),这是因为,每次在出队后要将数组后面...

    循环队列的顺序存储结构

    在上次,我们讲到的是,队列的顺序存储结构也是由ArrayList实现的,从此就可以看出,在入队时候的时间复杂度为O(1),但是在出队时候的时间复杂度为O(n),这是因为,每次在出队后要将数组后面的有效元素前移一位
    所以,这里就会用到循环队列,显然,这种队列也是顺序存储结构,在这个循环队列中也会去实现接口Queue。
    首先,我们要想到的是如何将一般的队列改变为循环队列。

    • 和之前一般的队列的顺寻存储结构一样,默认初始数组容量为10(循环队列的数组实际容量为11,这是因为要空出一个数组空间,至于为什么,将在后面进行解释);
    • 定义一个头指针front和尾指针rear,用这两个指针去维护循环队列中元素的入队和出队;
    • 定义一个size,去统计当前循环队列中的元素的有效个数;

    现在,我们先看一下循环队列是如何入队和出队的。
    初始时:
    在这里插入图片描述

    入队一个元素:
    在这里插入图片描述

    出队一个元素:
    在这里插入图片描述
    这样,front和rear指针就可以很轻松的去维护循环队列的入队和出队,并且它们的时间复杂度都为O(1),但是要注意特殊情况的存在,比如,当数组的0角标没有元素但7角标也有元素的时候,rear指针就要移动到front的前面,如下图所示:

    在这里插入图片描述

    这个时候很明显,循环队列已经满了,所以我们就会想到,如何判断循环队列什么时候为满,什么时候为空?

    其实,利用它的周期性可以很明显的得出结论:
    队列为满的时候:(rear+1)%n == front; (n为数组的总长度;如上图:(0+1)%8等于1也就是等于front指向的位置)
    如果出现这种情况,如下图示:
    在这里插入图片描述

    因为,我们每次的出队,front指针都会向后面移动一位,而rear指针是不会移动的,如果我们将上图的两个元素全部出队列,会出现这样的情况:
    在这里插入图片描述

    很显然,判断队列为空也为:(rear+1)%n == front;

    这样的话就会重复,所以这就是我们之前说,为什么要在创建循环队列数组的时候多创建一个元素空间的原因了。
    因此,判断队列为空的条件就为:rear == front;
    如下图:
    在这里插入图片描述

    如上图,我们现在入队一个元素:
    在这里插入图片描述

    每次在入队的时候,将rear指针始终指向队尾最后一个元素的空间。
    并且每次入队的时候,rear的变化也要注意:rear = (rear+1)%n;

    说了这么多,我们就来看一下具体的代码实现。
    首先和我们之前一样,先来看看它的顺序存储结构:

    package DS01.动态数组;
    import java.util.Iterator;
    /**
     * @author 七夏
     * @param <E>
     * @version 1.0
     * 循环队列:如果我们默认创建一个为容量为10的的循环队列时,我们须在该循环队列容量的基础上再加1,
     * 这是为了在判断循环队列是否为空时,起到作用
     *
     * 循环队列为满时的条件:(rear+1)%data.length 等于 front
     * 循环队列为空时的条件:front == rear
     * 元素每次进队时,队头front每次更新:front = (front+1)%data.length
     * 元素每次出队时,队尾rear每次更新:rear = (rear+1)%data.length
     * 函数 E getRear() 在获取队尾元素时的方法为:data[(rear-1+data.length)%data.length]
     */
    public class ArrayQueueLoop<E> implements Queue<E>{
    	//设置默认初始容量(后面会加1)
        private static final int DEFAULT_CAPACITY = 10;
        private E[] data;
        private int front;
        private int rear;
        private int size;
    
        public ArrayQueueLoop(){
            this(DEFAULT_CAPACITY);
        }
        public ArrayQueueLoop(int capacity){
            if(capacity <= 0){
                throw new IllegalArgumentException("指定容量错误:"+capacity);
            }
            data = (E[])(new Object[capacity+1]);//加1,让数组多出一个空间
            front = 0;
            rear = 0;
            size = 0;
        }
    }
    

    现在,看一下入队代码:

    	@Override
        public void enqueue(E e) {
        	//判断队列是否满
            if((rear + 1)%data.length == front){
                //扩容
                resize(data.length*2-1);
            }
            data[rear] = e;
            //更新rear队尾指针位置
            rear = (rear+1)%data.length;
            size++;
        }
    

    出队:

    	@Override
        public E dequeue() {
            if(isEmpty()){
                throw new IllegalArgumentException("队列为空");
            }
            //拿出对头元素
            E res = data[front];
            //更新front对头指针位置
            front = (front+1)%data.length;
            size--;
            //缩容
            if(size <= (data.length-1)/4 && (data.length-1)/2 >= 10){
                resize(data.length/2+1);
            }
            return res;
        }
    

    扩容:

    	private void resize(int newLen) {
            E[] newData = (E[])(new Object[newLen]);
            int p = front;
            int i = 0;
            while(true){
                newData[i] = data[p];
                i++;
                p = (p+1)%data.length;
                //如果p指针等于rear队尾指针时,结束循环
                if(p == rear){
                    break;
                }
            }
            /*
            上述while循环相当于下述for循环
            for(int i = 0,p = front;p != rear;i++,p = (p+1)%data.length){
    			newData[i] = data[p];
    		}
            */
            front = 0;
            rear = size;
            data = newData;
        }
    

    实现iterator方法:
    和之前都大致类似,在这里,我们在内部类中首先定义一个p指针,用来遍历循环队列,在hasNext函数中,只要p指针不等于rear队尾指针,说明该循环队列“尚不为空”(当前指向的元素后面还有元素);next函数中,创建res变量获取当前元素,之后将更新p指针的位置,最终返回res。

    	@Override
        public Iterator<E> iterator() {
            return new ArrayQueueLoopIterator();
        }
        private class ArrayQueueLoopIterator implements Iterator<E>{
            int p = front;
            @Override
            public boolean hasNext() {
                return p != rear;
            }
    
            @Override
            public E next() {
                E res = data[p];
                //更新p指针的指向位置
                p = (p+1)%data.length;
                return res;
            }
        }
    

    其他方法:
    在这些方法中,我们要注意toString方法和getRear方法,在getRear方法中,我们直接返回data[(rear-1+data.length)%data.length]。

    	@Override
        public int getSize() {
            return size;
        }
    
        @Override
        public boolean isEmpty() {
            return size == 0 && front == rear;
        }
        @Override
        public E getFront() {
            if(isEmpty()){
                throw new IllegalArgumentException("队列为空");
            }
            return data[front];
        }
    
        @Override
        public E getRear() {
            if(isEmpty()){
                throw new IllegalArgumentException("队列为空");
            }
            return data[(rear-1+data.length)%data.length];
        }
    
        @Override
        public void clear() {
            data = (E[])(new Object[DEFAULT_CAPACITY+1]);
            front = 0;
            rear = 0;
            size = 0;
        }
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append(String.format("ArrayQueue: %d/%d \n",getSize(),data.length-1));
            sb.append('[');
            if(isEmpty()){
                sb.append(']');
            }else{
                for (int i = front; i != rear; i = (i+1)%data.length) {
                    sb.append(data[i]);
                    if((i+1)%data.length == rear){
                        sb.append(']');
                    }else{
                        sb.append(',');
                    }
                }
            }
            return sb.toString();
        }
    
    展开全文
  • 队列——顺序存储结构循环队列

    千次阅读 2013-05-31 11:27:16
    队列顺序存储结构   为什么小甲鱼上节课说队列的实现上我们更愿意用链式存储结构来存储? 我们先按照应有的思路来考虑下如何构造队列顺序存储结构,然后发掘都遇到了什么麻烦。 我们假设队列有...

    http://blog.fishc.com/2155.html

    队列的顺序存储结构

     

    为什么小甲鱼上节课说队列的实现上我们更愿意用链式存储结构来存储?

    我们先按照应有的思路来考虑下如何构造队列的顺序存储结构,然后发掘都遇到了什么麻烦。

    我们假设一个队列有n个元素,则顺序存储的队列需建立一个大于n的存储单元,并把队列的所有元素存储在数组的前n个单元,数组下标为0的一端则是队头。

     

    No Pic You Say a J8

     

    队列的顺序存储结构

    入队列操作其实就是在队尾追加一个元素,不需要任何移动,时间复杂度为O(1)。

    出队列则不同,因为我们已经架设下标为0的位置是队列的队头,因此每次出队列操作所有元素都要向前移动。

     

    队列的顺序存储结构

    在现实中也是如此,一群人在排队买火车票,前边的人买好了离开,后面的人就要全部向前一步补上空位。

    可是我们研究数据结构和算法的一个根本目的就是要想方设法提高我们的程序的效率,按刚才的方式,出队列的时间复杂度是O(n),效率大打折扣!

    如果我们不去限制队头一定要在下标为0的位置,那么出队列的操作就不需要移动全体元素。

     

    队列的顺序存储结构

    但是这样也会出现一些问题,例如按下边的情形继续入队列,就会出现数组越界的错误。

     

    队列的顺序存储结构

    可事实上我们有0和1两个下标还空着,这叫假溢出。

     

    循环队列定义

     

    我们再想想,要解决假溢出的办法就是如果后面满了,就再从头开始,也就是头尾相接的循环。

    循环队列它的容量是固定的,并且它的队头和队尾指针都可以随着元素入出队列而发生改变,这样循环队列逻辑上就好像是一个环形存储空间。

     

    但要注意的是,在实际的内存当中,不可能有真正的环形存储区,我们只是用顺序表模拟出来的逻辑上的循环。

    我们通过一段动画片来加深印象吧!

     

    循环队列

     

    于是我们发觉了,似乎循环队列的实现只需要灵活改变front和rear指针即可。

    也就是让front或rear指针不断加1,即时超出了地址范围,也会自动从头开始。我们可以采取取模运算处理:

    (rear+1) % QueueSize

    (front+1) % QueueSize

     

    取模就是取余数的意思,他取到的值永远不会大于除数,大家结合实例拿张纸算一算就知道啦~

    定义一个循环队列

    #define MAXSIZE 100
    typedef struct
    {
    	ElemType *base; // 用于存放内存分配基地址
    					// 这里你也可以用数组存放
    	int front;
    	int rear;
    }


    初始化一个循环队列

    initQueue(cycleQueue *q)
    {
    	q->base = (ElemType *) malloc (MAXSIZE * sizeof(ElemType));
    	if( !q->base )
    		exit(0);
     
    	q->front = q->rear = 0;
    }


    入队列操作

    InsertQueue(cycleQueue *q, ElemType e)
    {
    	if( (q->rear+1)%MAXSIZE == q->front )
    		return; // 队列已满
     
    	q->base[q->rear] = e;
    	q->rear = (q->rear+1) % MAXSIZE;
    }


    出队列操作

    DeleteQueue(cycleQueue *q, ElemType *e)
    {
    	if( q->front == q->rear )
    		return ; // 队列为空
     
    	*e = q->base[q->front];
    	q->front = (q->front+1) % MAXSIZE;
    }


    人生如栈

     

    人生,就像是栈的演变。

    在父亲忙碌的入栈、出栈操作中,你,诞生了!

     

    人生,仿佛是栈的重现。

    每天你奔波于事业与家庭之间,做着似乎总是重复的事情,为的只是一餐温饱。

     

    你总说,在哪里跌倒就在哪里爬起来,但是,你发现似乎总是在同一个地方跌倒无数次!

    有一那么一次,你弹栈找不到返回地址,你忧郁了,迷茫了。。。。。。

     

    很幸运,你看到了小甲鱼的视频^_^

    他会告诉你,在一个个栈的外边,其实隐藏着一个队列在调用你的每一个栈,只是你还年轻,没办法看得太清楚。

     

    但是,你抬头仰望星空,在孤独中多思考,在彷徨中多回顾,就有希望,不断进取,就能成功!

    人生,又是一个大队列的实现,春夏秋冬年复一年,改变的是时间,不变的是你对未来执着的信念!

     

    地球近似于圆形,但并不完美。

    选错了方向,你可能要多走一些路,

    但,只要你肯坚持到底,你都可以到达终点!


    展开全文
  • 队列的顺序存储结构循环队列

    千次阅读 2016-11-12 10:31:54
    队列(queue)是只允许...队列顺序存储结构使用数组的实现,假设数组长度为N,这时删除队头元素的时候,这个元素后面的每个元素都要移动,这样就会出队的性能会下降。如下图所示: 删除队首的元素A1,那么后面的

    队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。
    队列是一种先进先出(First In First Out)的线性表,简称FIFO.允许插入的一端称为队尾,允许删除的一端称为队头。
    队列的顺序存储结构使用数组的实现,假设数组长度为N,这时删除队头元素的时候,这个元素后面的每一个元素都要移动,这样就会出队的性能会下降。如下图所示:
    这里写图片描述
    删除队首的元素A1,那么后面的其他元素都要移动到这个位置,这样会造成出队性能下降。
    现在假设我们删除了之后队列中的其余元素位置不变,是不是就可以解决了这个问题。
    那样是可以,但是又会引发新的问题,
    现在队列中有5个元素已经满了,让A1,A2,A3都出队,这个时候会空出3个位置,如下图
    这里写图片描述
    这个时候我们同样也是不可以在入队了,然而队列中还是有空间的,我们想要使用这个剩余空间,这个时候我们是要在下标为0的位置放置元素,这样数组的空间就可以充分利用。这样这个数组就相当于一个头尾相接的循环。我们把这种头尾相接的的顺序存储结构称为循环队列。相当于下图
    这里写图片描述
    当下标为4的位置有元素,在想添加元素的时候,就放到下标为0的位置。
    队列引入了两个指针front,rear.
    front指针指向队头的元素,rear指针指向队尾元素的下一个位置。
    比如上图中 A3是队首元素 所以front指向它,A4是队尾元素,所以rear指向它下一个位置。
    假设队列的长度为QueueSize,
    那么front和rear下一个位置的下标的分别为 (front+1)%QueueSize ,(rear+1)%QueueSize;
    队列的长度的计算公式为: (rear-front+QueueSize)%QueueSize;
    队列为空的条件 :front ==rear
    队列满时的条件: (rear+1)%QueueSize == front
    下面是使用代码演示循环队列的用法:

    #include <stdio.h>
    #define MAX_SIZE 5
    
    typedef struct Queue
    {
        int data[MAX_SIZE];
        int front;
        int rear;
    }QUEUE,*PQUEUE;
    
    void initQueue(PQUEUE);//循环队列初始化
    bool addQueue(PQUEUE,int);//循环队列添加
    bool deleteQueue(PQUEUE,int*);//循环队列删除
    bool isFull(PQUEUE);//循环队列是否已满
    bool isEmpty(PQUEUE);//循环队列是否为空
    void showQueue(PQUEUE);//打印
    int main(void)
    {
        QUEUE Queue;
        int pVal;
        initQueue(&Queue);
        addQueue(&Queue,30);
        addQueue(&Queue,60);
        addQueue(&Queue,100);
        showQueue(&Queue);
        if(deleteQueue(&Queue,&pVal))
        printf("删除的元素是: %d\n",pVal);
        addQueue(&Queue,-100);
        addQueue(&Queue,-900);
        showQueue(&Queue);
        return 0;
    }
    
    void showQueue(PQUEUE p)
    {
        int front = p->front;
        int rear = p->rear;
        while((front)%MAX_SIZE!=rear)
        {
            printf("%d  ",p->data[front]);
            front = (front+1)%MAX_SIZE;
        }
        printf("\n");
    
    }
    
    bool isFull(PQUEUE p)
    {
        if((p->rear+1)%MAX_SIZE==p->front)
        {
            return true;
        }
        return false;
    }
    bool isEmpty(PQUEUE p)
    {
        if(p->rear==p->front)
        {
            return true;
        }
        return false;
    }
    
    
    void initQueue(PQUEUE q)
    {
        q->front = 0;
        q->rear = 0;
    }
    
    bool addQueue(PQUEUE p,int e)
    {
        if(isFull(p))
        {
            return false;
        }
        p->data[p->rear] = e;
        p->rear = (p->rear+1)%MAX_SIZE;//下标移动到下一个位置
        return true;
    }
    
    bool deleteQueue(PQUEUE p,int * pVal)
    {
        if(isEmpty(p))
        {
            return false;
        }
        *pVal = p->data[p->front];
        p->front=(p->front+1)%MAX_SIZE;
        return true;
    }
    展开全文
  •   队列(Queue) 简称队,也是一种操作受限的线性表,只允许在表的一端进行插入,而在表的另一端进行删除。向队列中插入元素称为入队或进队。删除元素称为出队或离队。这和我们日常生活中的排队是一致的,最早排队的...

    一、队列的基本概念

    1.1 队列的定义

      队列(Queue) 简称队,也是一种操作受限的线性表,只允许在表的一端进行插入,而在表的另一端进行删除。向队列中插入元素称为入队进队。删除元素称为出队离队。这和我们日常生活中的排队是一致的,最早排队的也是最早离队的,其操
    作的特性是先进先出(First In First Out, FIFO),如:
    在这里插入图片描述
    队头(Front): 允许删除的一-端,又称队首。
    队尾(Rear)。: 允许插入的一-端。
    空队列: 不含任何元素的空表。

    1.2 队列常见的基本操作

    InitQueue(&Q): 初始化队列,构造-一个空队列 Q.
    QueueEmpty(Q): 判队列空,若队列Q为空返回true,否则返回false.
    EnQueue(&Q,x): 入队,若队列Q未满,将x加入,使之成为新的队尾。
    DeQueue (&Q, &x): 出队,若队列e非空,删除队头元素,并用x返回。
    GetHead(Q,&x): 读队头元素,若队列Q非空,则将队头元素赋值给x。

    注意: 栈和队列是操作受限的线性表,因此不是任何对线性表的操作都可以作为栈 和队列的操作。比如,不可以随便读取栈或队列中间的某个数据。

    二、队列的顺序存储结构

      队列的顺序实现是指分配一块连续的存储单元存放队列中的元素,并附设两个指针:队头指针front 指向队头元素,队尾指针rear 指向队尾元素的下一个位置 (也可以让rear指向队尾元素、front 指向队头元素) 。
      顺序结构可描述为:

    typedef struct SqQueue
    {
    	ElemType data[MaxSize];	//存放队列元素
    	int front;	//队头指针
    	int rear;	//队尾指针
    }SqQueue;
    

      初始状态(队空条件):Q.front==Q.rear==0
      进队操作:队不满时,先送值到队尾元素,再将队尾指针加1。
      出队操作:队不空时,先取队头元素值,再将队头指针加1。

    队列的操作:
    在这里插入图片描述

    顺序存储结构存在的问题:

    在这里插入图片描述
      出队a1、a2,则front指针指向下标为2的位置,rear 不变,如左图所示,再入队a5,此时front 指针不变,rear 指针移动到数组之外。嗯?数组之外,那么就会产生数组越界的错误,可实际上,我们的队列在下标为0和1的地方还是空闲的。我们把这种现象叫做 “假溢出”。如右图所示。

    三、循环队列

      为了解决假溢出的问题,引入了循环队列,使其头尾相连。我们把队列的这种头尾相接的顺序存储结构称为循环队列。

    3.1 实现思路

      当队首指针Q. front=MaxSize-1后,.再前进一个位置就自动到0,这可以利用 除法取余运算(%) 来实现。.
      初始时: Q.front=Q.rear=0
      队首指针进 1: Q.front= (Q.front+1) % MaxSize
      队尾指针进 1: Q.rear= (Q.rear+1) % MaxSize
      队列长度: (Q. rear +MaxSize-Q. front) % MaxSize
      出队入队时:指针都按顺时针方向进1 (如图所示)

    3.2 循环队列队空和队满的判断条件

      循环队列队空和队满的判断条件是什么呢?显然,队空的条件是Q.front==Q.rear
    若入队元素的速度快于出队元素的速度,则队尾指针很快就会赶上队首指针,如图(d1)所示,此时可以看出队满时也有Q.front==Q.rear
      为了区分队空还是队满的情况,有三种处理方式:

    1. 牺牲一个单元来区分队空和队满,入队时少用一个队列单元,这是一种较为普遍的做法,
      约定以 “队头指针在队尾指针的下一位置作为队满的标志”,如图(d2)所示。
      队满条件: (Q.rear+1) % MaxSize==Q.front
      队空条件仍为: Q.front==Q.rear。
      队列中元素的个数: (Q. rear-Q. front+MaxSize)各MaxSize.
    2. 类型中增设表示元素个数的数据成员。这样,队空的条件为Q.size==0;队满的条件为
      Q.size==MaxSize。这两种情况都有Q. front==Q. rear.
    3. 类型中设置一个标志变量 flag,以区分是队满还是队空。flag 等于 0 时,若因删除导致
      Q.frontQ.rear ,则为队空; flag 等于 1 时,若因插入导致Q. frontQ. rear,则为队满。(常用
      在这里插入图片描述

    3.3 循环队列的操作

    #include<stdio.h>
    #include<malloc.h>
    
    
    #define MaxSize 20
    typedef int ElemType;
    
    typedef struct SqQueue
    {
    	ElemType *data;	//存放队列元素
    	int front;	//队头指针
    	int rear;	//队尾指针
    }SqQueue;
    
    void InitQueue(SqQueue *Q);	//初始化队列
    bool isEmpty(SqQueue Q);	//判断队列是否为空
    bool isFull(SqQueue Q);	//判断队列是否已满
    bool EnQueue(SqQueue *Q,ElemType e);	//入队
    bool DeQueue(SqQueue *Q,ElemType *e);	//出队
    void PrintQueue(SqQueue pQ);
    
    int main()
    {
    	SqQueue Q;
    	ElemType e;
    	InitQueue(&Q);
    
    	EnQueue(&Q,1);
    	EnQueue(&Q,2);
    	EnQueue(&Q,3);
    	EnQueue(&Q,4);
    	EnQueue(&Q,5);
    	EnQueue(&Q,6);
    	EnQueue(&Q,7);
    	
    	PrintQueue(Q);
    
    	if(DeQueue(&Q,&e))
    		printf("出队成功,出队元素为:%d\n",e);
    	else
    		printf("出队失败\n");
    
    	PrintQueue(Q);
    
    	return 0;
    }
    
    
    void InitQueue(SqQueue *Q)
    {
    	Q->data = (ElemType *)malloc(sizeof(ElemType)* MaxSize);
    	Q->front = Q->rear = 0;
    }
    
    
    bool isEmpty(SqQueue Q)
    {
    	if(Q.rear == Q.front)
    		return true;
    	else
    		return false;
    }
    
    bool isFull(SqQueue Q)
    {
    	if((Q.rear + 1) % MaxSize == Q.front)
    		return true;
    	else
    		return false;
    }
    
    bool EnQueue(SqQueue *Q,ElemType e)
    {
    	if((Q->rear + 1) % MaxSize == Q->front)
    		return false;	//队满报错
    	Q->data[Q->rear] = e;
    	Q->rear = (Q->rear +1) % MaxSize;	//队尾指针加1取模
    	return true;
    }
    
    bool DeQueue(SqQueue *Q,ElemType *e)
    {
    	if(Q->rear == Q->front)
    		return false;	//队空报错
    	*e = Q->data[Q->front];
    	Q->front = (Q->front +1) % MaxSize;	//队头指针加1取模
    	return true;
    }
    
    void PrintQueue(SqQueue pQ)
    {
    	int i = pQ.front;
    
    	while(i != pQ.rear)
    	{
    		printf("%d ",pQ.data[i]);
    		i = (i+1) % MaxSize;
    	}
    	printf("\n");
    }
    

    四、队列的链式存储结构

    4.1 队列链式存储

      队列的链式表示称为链队列,它实际上是一个同时带有队头指针和队尾指针的单链表。头指
    针指向队头结点,尾指针指向队尾结点,即单链表的最后一个结点
      队列的链式存储如图:
    在这里插入图片描述
    可描述为:

    typedef struct QNode	/* 结点结构 */
    {
       ElemType data;
       struct QNode *next;
    }QNode,*QueuePtr;
    
    typedef struct			/* 队列的链表结构 */
    {
       QueuePtr front,rear; /* 队头、队尾指针 */
    }LinkQueue;
    

      当Q. front==NULLQ.rear==NULL时,链式队列为空。
      出队时,首先判断队是否为空,若不空,则取出队头元素,将其从链表中摘除,并让Q. front
    指向下一个结点(若该结点为最后一个结点,则置Q. front和Q. rear都为NULL)。入队时,
    建立一个新结点,将新结点插入到链表的尾部,并改让Q. rear指向这个新插入的结点(若原队列为空队,则令Q. front也指向该结点)。
      不带头结点的链式队列在操作上往往比较麻烦,因此通常将链式队列设计成一个带头结点的单链表,这样插入和删除操作就统一了。
    在这里插入图片描述

    使用场景: 用单链表表示的链式队列特别适合于数据元素变动比较大的情形,而且不存在队列满且产生溢出的问题。另外,假如程序中要使用多个队列,与多个栈的情形一样,最好使用链式
    队列,这样就不会出现存储分配不合理和“溢出”的问题。

    4.2 链式队列的基本操作

    4.2.1 初始化

    void InitQueue(LinkQueue *Q)
    { 
    	Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
    	Q->front->next=NULL;
    }
    

    4.2.2 判队空

    bool IsEmpty(LinkQueue Q)
    { 
    	if(Q.front==Q.rear)
    		return true;
    	else
    		return false;
    }
    

    4.2.3 入队

      入队操作时,其实就是在链表尾部插入结点,如图所示:
    在这里插入图片描述
    其代码如下:

    bool EnQueue(LinkQueue *Q,ElemType e)
    { 
    	QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
    	s->data=e;
    	s->next=NULL;
    	Q->rear->next=s;	/* 把拥有元素e的新结点s赋值给原队尾结点的后继,见图中① */
    	Q->rear=s;		/* 把当前的s设置为队尾结点,rear指向s,见图中② */
    	return true;
    }
    

    4.2.4 出队

      出队操作时,就是头结点的后继结点出队,将头结点的后继改为它后面的结点,若链表除头结点外只剩一个元素时,则需将rear 指向头结点,如图所示:
    在这里插入图片描述

    其代码如下:

    bool DeQueue(LinkQueue *Q,ElemType *e)
    {
    	QueuePtr p;
    	if(Q->front==Q->rear)
    		return false;
    	p=Q->front->next;		/* 将欲删除的队头结点暂存给p,见图中① */
    	*e=p->data;				/* 将欲删除的队头结点的值赋值给e */
    	Q->front->next=p->next;/* 将原队头结点的后继p->next赋值给头结点后继,见图中② */
    	if(Q->rear==p)		/* 若队头就是队尾,则删除后将rear指向头结点,见图中③ */
    		Q->rear=Q->front;
    	free(p);
    	return true;
    }
    

    4.3 队列链式结构完整代码

    #include<stdio.h>
    #include<malloc.h>
    
    #define MaxSize 10;
    typedef int ElemType;
    
    typedef struct QNode	/* 结点结构 */
    {
       ElemType data;
       struct QNode *next;
    }QNode,*QueuePtr;
    
    typedef struct			/* 队列的链表结构 */
    {
       QueuePtr front,rear; /* 队头、队尾指针 */
    }LinkQueue;
    
    
    /* 构造一个空队列Q */
    void InitQueue(LinkQueue *Q)
    { 
    	Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
    	Q->front->next=NULL;
    }
    
    bool IsEmpty(LinkQueue Q)
    { 
    	if(Q.front==Q.rear)
    		return true;
    	else
    		return false;
    }
    
    /* 插入元素e为Q的新的队尾元素 */
    bool EnQueue(LinkQueue *Q,ElemType e)
    { 
    	QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
    	s->data=e;
    	s->next=NULL;
    	Q->rear->next=s;	/* 把拥有元素e的新结点s赋值给原队尾结点的后继,见图中① */
    	Q->rear=s;		/* 把当前的s设置为队尾结点,rear指向s,见图中② */
    	return true;
    }
    
    
    
    /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
    bool DeQueue(LinkQueue *Q,ElemType *e)
    {
    	QueuePtr p;
    	if(Q->front==Q->rear)
    		return false;
    	p=Q->front->next;		/* 将欲删除的队头结点暂存给p,见图中① */
    	*e=p->data;				/* 将欲删除的队头结点的值赋值给e */
    	Q->front->next=p->next;/* 将原队头结点的后继p->next赋值给头结点后继,见图中② */
    	if(Q->rear==p)		/* 若队头就是队尾,则删除后将rear指向头结点,见图中③ */
    		Q->rear=Q->front;
    	free(p);
    	return true;
    }
    
    
    void PrintQueue(LinkQueue Q)
    {
    	QueuePtr p;
    	p=Q.front->next;
    	while(p)
    	{
    		 printf("%d ",p->data);
    		 p=p->next;
    	}
    	printf("\n");
    }
    
    int main()
    {
    	LinkQueue Q;
    	ElemType e;
    
    	InitQueue(&Q);
    
    	EnQueue(&Q,1);
    	EnQueue(&Q,2);
    	EnQueue(&Q,3);
    	EnQueue(&Q,4);
    	EnQueue(&Q,5);
    	EnQueue(&Q,6);
    	EnQueue(&Q,7);
    	
    	PrintQueue(Q);
    
    	if(DeQueue(&Q,&e))
    		printf("出队成功,出队元素为:%d\n",e);
    	else
    		printf("出队失败\n");
    
    	PrintQueue(Q);
    
    
    	return 0;
    }
    
    展开全文
  • 我们在《栈的顺序存储结构》中发现,栈操作的top指针在Push时增大而在Pop时减小,栈空间是可以重复利用的,而队列的front、rear指针都在一直增大,虽然前面的元素已经出队了,但它所占的存储空间却不能重复利用。...
  • 队列也是线性表的一种特殊形式,它只允许在线性表的一端进行插入,而在另一端进行删除,也就是所谓的先入先出 用顺序存储的结构实现队列,假如队列有n个元素,则必须建立大于...将原本的顺序存储结构进行首尾相接得...
  • 顺序存储的队列,元素循环存储循环队列定义循环队列判空、判满循环队列长度代码实现测试结果 循环队列定义 在逻辑上把顺序存储的队列想象成个环,就是循环队列循环队列仍是顺序存储,只是元素可以循环存储在...
  • 队列一种先进先出(First In First out)的线性表,允许插入的一端称为队尾,允许删除的一端称为队头。 3. 队列顺序存储有什么不足? 使用数组实现的顺序存储,当做出队列操作时,所有的元素都需要向前移动一...
  • 顺序存储的队列写起来跟顺序实现的栈很像,也是采用数组存储数据,但是在不断入队列和出队列过程中,数据会不断后移,所以会造成大量的空间浪费,所以这里我们采用循环队列的形式 循环队列长度 我们需要知道,循环...
  • 队列队列顺序存储结构、链式存储结构
  • 循环队列循环队列存储结构typedef int QElemType; typedef struct{ QElemType *base; int front; int rear; }SqQueue; 实现循环语句 可以把循环队列想象成个圈 因为循环队列假如是数据能占所
  • 队列顺序存储结构

    千次阅读 2018-05-05 16:11:55
    队列顺序存储结构:要预先分配内存,知道队列的最大长度。初始化队列时Q.rear=Q.front=0;对尾插入队列元素rear+1,对头删除队列元素front+1,假设当前为队列分配的最大空间为6,则当队列处于图(d)时,再插入元素...
  • 队列的顺序存储实现—循环队列

    千次阅读 2015-04-17 21:37:40
    由于队列也是一种线性表,所以队列的实现也有顺序存储和链式存储这两种实现。当队列顺序存储时,入队列的操作所需要的时间复杂度为O(1),而出队列的时间复杂度为O(n),因为删除队头元素,需要将后面
  • 数据结构_《大话数据结构》_队列_顺序存储结构队列/链式存储结构队列
  • 循环顺序队列的另一种实现方式,即少用一个存储空间来实现循环顺序队列
  • 2. 掌握栈的顺序存储结构和链式存储结构的实现;3. 熟悉队列的特点(先进先出)及队列的抽象类定义;4. 掌握栈的顺序存储结构和链式存储结构的实现;二、实验要求1. 复习课本中有关栈和队列的知识;2. 用C++...
  • 这次介绍的是循环队列,介绍循环队列之前,先介绍一下队列的概念。队列(Queue):入队(添加数据)操作限定在队尾(Rear),其他操作限定在队头(Front)的线性表,当队列中没有数据元素时称为空队列。 队列也有两...
  • 数据结构 - 队列静态顺序存储结构

    千次阅读 2015-04-29 09:53:42
    一种先进先出(First In First Out ,简称FIFO)的线性表。只允许在表的一端进行插入,而在另一端进行删除。 队首(front) :允许进行删除的一端称为队首。 队尾(rear) :允许进行插入的一端称为队尾。  例如:...
  • 队列(queue)是只允许在一端进行插入操作,而在另...循环队列一种头尾相接的顺序存储结构。 具体实现代码如下: /* SqQueue.h 头文件 */ /*循环队列,保留一个元素空间为空,用来区分队列是满还是空*/ #include
  • 循环队列 链式队列 循环顺序队列实现 链式队列实现 栈和队列总结 队列的定义 队列(queue)是只允许在一端进行插入操作,另一端进行删除操作的线性表。 队列是一种先进先出的线性表,允许插入的一端称为队尾...
  • 循环队列顺序存储

    2016-03-20 10:57:59
    对于队列顺序存储结构,如果要将第个元素存在数组的第个位置,则之后在插入和删除时平均要移动n个元素,时间复杂度为O(n); 细细想来,其实不把第个元素放在第个位置上也可以,这种方案不仅仅是增强了...
  • 线性表和栈分别是顺序存储结构和链式存储结构的代表,而队列和栈可以用以上两数据结构进行表达,不过是把它们的成员函数加一改动,主要是限制为先进先出和后进先出的功能,本文主要介绍队列顺序存储结构,这里...
  • 队列也是一种线性表,是一种先进先出的线性结构队列只允许在表的一端进行插入(入队)、删除(出队)操作。允许插入的一端称为队尾,允许删除的一端称为队头。 &amp;nbsp; &amp;nbsp; &amp;nbsp; &...
  • 1、队列顺序存储 队列的顺序实现是指分配块连续的存储单元存放队列中的元素,并附设两个指针:队头指针front指向队头元素。队尾指针rear指向队尾元素的下个位置(其实和单链表有无头结点是一样的,队尾指针你...
  • 循环队列顺序储存结构 文章目录循环队列顺序储存结构队列的基本定义队列的基本操作初始化队列求队列长度入队列操作出队列函数打印该队列项目整体源代码: 队列的基本定义 队列是只允许在一端进行插入操作,而在...
  • 队列一种先进先出的线性表(FIFO),出队列的那一端叫做队头,入队列的那一端叫做队尾。作为线性表,同样也有各种端口操作,不同的是插入数据只能在队尾进行,删除数据只能在队头进行。  同栈,队列也有两存储...
  • 最常见的就是去超市买菜称重时大妈们排得贼长的队列(这是理想情况,通常是围成圈),还有超市结账的队伍,还有以前食堂打饭的队伍。是不是很有印象呢~~~ 那队列有什么特点呢? 就拿食堂打饭来说,下课...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 87,868
精华内容 35,147
关键字:

循环队列是队列的一种顺序存储结构