精华内容
下载资源
问答
  • 你是不是有个疑问,关于循环队列循环队列的头指针和尾指针的时候,直接加减不就好了,为什么要取模呢? 解决 循环队列的概念: 出队时:Q.Front++ 入队时:Q.Front++ 这样每次不管是入队还是出队,指针数...

    问题

    你是不是有个疑问,关于循环队列,在取循环队列的头指针和尾指针的时候,直接加减不就好了,为什么要取模呢?

    解决

    循环队列的概念:
    循环队列是把顺序队列首尾相连,把存储队列元素的表从逻辑上看成一个环,成为循环队列。

    在这里插入图片描述

    • 出队时:Q.Front++
    • 入队时:Q.Front++

    这样每次不管是入队还是出队,指针数都会++,如果不取模,就容易造成指针溢出。

    展开全文
  • 如 Q.rear=(Q.rear+1)%Q.queuesize; 为什么不能直接写Q.rear=(Q.rear+1)啊?
  • 循环队列

    2020-07-07 17:47:24
    * 在循环队列中,设置两个索引front、tail * 当front == tail时,队列为空 * 当tail+1 == front时,队列满:(tail +1)%data.length == front * 在循环队列中浪费一个空间 * 循环队列不再使用之前我们实现的动态...

    循环队列

    • 循环队列,解决出队列时时间复杂度是O(n)的问题
    • 在循环队列中,设置两个索引front、tail
    • 当front == tail时,队列为空
    • 当tail+1 == front时,队列满:(tail +1)%data.length == front
    • 在循环队列中浪费一个空间
    • 循环队列不再使用之前我们实现的动态数组作为底层实现
    • 循环队列的出队的时间复杂度与入队的时间复杂度均为O(1),均摊时间复杂度
    /**
     * 循环队列,解决出队列时时间复杂度是O(n)的问题
     * 在循环队列中,设置两个索引front、tail
     * 当front == tail时,队列为空
     * 当tail+1 == front时,队列满:(tail +1)%data.length == front
     * 在循环队列中浪费一个空间
     * 循环队列不再使用之前我们实现的动态数组作为底层实现
     * 循环队列的出队的时间复杂度与入队的时间复杂度均为O(1),均摊时间复杂度
     *
     * @author f242
     * @since V1.0.0
     * 2020-03-21 15:00
     */
    public class LoopQueue<E> implements Queue<E>{
    
        private E[] data;
        private int front,tail;
        private int size;
    
        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 boolean isEmpty(){
            return front == tail;
        }
    
        @Override
        public int getSize(){
            return size;
        }
    
        @Override
        public void enqueue(E e){
            //判断当前队列是否满
            if((tail +1)%data.length == front){
                //扩容
                resize(2 * getCapacity());
            }
            data[tail] = e;
            tail = (tail+1) % data.length;
            size ++;
        }
        @Override
        public E dequeue(){
            if(isEmpty()){
                throw  new IllegalArgumentException("Cannot dequeue from an empty queue");
            }
            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("Queue is Empty");
            }
            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[(i+front)%data.length];
            }
            data = newData;
            front = 0;
            tail = size;
        }
    
        @Override
        public String toString(){
            StringBuilder res = new StringBuilder();
            res.append(String.format("LoopQueue: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();
        }
    }
    
    
    展开全文
  • 在循环队列中,空队特征是front = rear, 队满时也会有front = rear; 判断条件将出现二义性; 解决方法 1、使用额外的标记 (1)引入Size标记 来记录队列的长度,当size为队列最大长度时为满,size=0为空; (2...

    循环队列样式结构图:
    在这里插入图片描述
    优点:
    解决了顺序队列只能从队尾插入元素而导致空间的浪费;
    问题:
    在循环队列中,空队特征是front = rear, 队满时也会有front = rear; 判断条件将出现二义性;

    解决方法

    1、使用额外的标记
    (1)引入Size标记
    来记录队列的长度,当size为队列最大长度时为满,size=0为空;
    (2)引入tag标记
    删除时tag=0,插入时tag=1;当front == rear时,如果 tag==0则为空,否则为满;
    2、仅使用n-1个数组空间

    空闲单元法:

    在这里插入图片描述
    循环队列满的条件:
    (rear+1)% N == front;
    循环队列空的条件:
    (front==rear);

    展开全文
  • 循环队列应用

    2018-11-06 23:10:50
    郭艳数据结构作业之循环队列的应用与斐波拉契。题目如下: 在K_Fib.h文件中K_Fib()函数实现计算并输出K阶斐波那契序列...在算法执行结束时,留在循环队列中的元素应是所求K阶斐波那契序列中的最后K项f(n-k+1),…,fn。
  • 泛型循环队列

    2021-06-12 20:01:54
    前言 循环队列是把顺序队列首尾相连,把存储队列元素的表从逻辑上看成一个环,成为循环队列。...在循环队列中,当队列为空时,有front=tail,而当所有队列空间全占满时,也有front=tail。为了区别这两种情

    前言

    循环队列是把顺序队列首尾相连,把存储队列元素的表从逻辑上看成一个环,成为循环队列。其将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用。在循环队列结构中,当存储空间的最后一个位置已被使用而再要进入队运算时,只需要存储空间的第一个位置空闲,便可将元素加入到第一个位置,即将存储空间的第一个位置作为队尾。循环队列可以更简单防止伪溢出的发生,但队列大小是固定的。在循环队列中,当队列为空时,有front=tail,而当所有队列空间全占满时,也有front=tail。为了区别这两种情况,规定循环队列最多只能有capacity-1个队列元素,当循环队列中只剩下一个空存储单元时,队列就已经满了。因此,队列判空的条件是front=tail,而队列判满的条件是front =(tail+1)%capacity,如下图所示:

    在这里插入图片描述

    具体实现

    • 接口
    public interface Queue<T> {
    
        /**
         * 添加元素
         * @param t
         */
        void enqueue(T t);
    
        /**
         * 元素出队
         * @return
         */
        T dequeue();
    
        /**
         * 获取队首元素
         * @return
         */
        T getFront();
    
        /**
         * 获取队列长度
         * @return
         */
        int getSize();
    
        /**
         * 是否为空
         * @return
         */
        boolean isEmpty();
    }
    
    • 实现类
    public class LoopQueue<T> implements Queue<T> {
    
        /**
         * 数组
         */
        private T[] data;
    
        /**
         * 元素起始与结束位置
         */
        private int front, tail;
    
        /**
         * 大小
         */
        private int size;
    
        /**
         * 构造函数
         * @param capacity
         */
        public LoopQueue(int capacity) {
            data = (T[]) new Object[capacity + 1];
            front = 0;
            tail = 0;
            size = 0;
        }
    
        /**
         * 无参构造函数
         */
        public LoopQueue() {
            this(10);
        }
    
        /**
         * 获取容量
         * @return
         */
        public int getCapacity() {
            return data.length - 1;
        }
    
        /**
         * 是否为空
         * @return
         */
        @Override
        public boolean isEmpty() {
            return front == tail;
        }
    
        /**
         * 获取大小
         * @return
         */
        @Override
        public int getSize() {
            return size;
        }
    
        /**
         * 添加元素
         * @param t
         */
        @Override
        public void enqueue(T t) {
            if ((tail + 1) % data.length == front) {
                // 数组扩容
                resize(2 * getCapacity());
            }
    
            data[tail] = t;
            tail = (tail + 1) % data.length;
            size ++;
        }
    
        /**
         * 数组增减容
         * @param newCapacity
         */
        private void resize(int newCapacity) {
            T[] newData = (T[]) new Object[newCapacity + 1];
    
            for (int i = 0; i < size; i++) {
                newData[i] = data[(i + front) % data.length];
            }
    
            data = newData;
            front = 0;
            tail = size;
        }
    
        /**
         * 元素出队
         * @return
         */
        @Override
        public T dequeue() {
            if (isEmpty()) {
                throw new IllegalArgumentException("Cannot dequeue from an empty dequeue.");
            }
    
            T res = data[front];
            data[front] = null;
            front = (front + 1) % data.length;
            size --;
    
            // 数组减容
            if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
                resize(getCapacity() / 2);
            }
    
            return res;
        }
    
        /**
         * 获取队首元素
         * @return
         */
        @Override
        public T getFront() {
            if (isEmpty()) {
                throw new IllegalArgumentException("Queue is Empty.");
            }
            return data[front];
        }
    
        /**
         * 重写toString方法
         * @return
         */
        @Override
        public String toString() {
            StringBuilder resp = new StringBuilder();
            resp.append(String.format("Queue: size = %d, capacity = %d, front [", size, getCapacity()));
            for (int i = front; i != tail; i = (i + 1) % data.length) {
                resp.append(data[i]);
    
                if ((i + 1) % data.length != tail) {
                    resp.append(",");
                }
    
            }
    
            resp.append("] tail");
    
            return resp.toString();
        }
    
        public static void main(String[] args) {
            LoopQueue<Integer> arrayQueue = new LoopQueue<>();
            for (int i = 0; i < 10; i++) {
                arrayQueue.enqueue(i);
                System.out.println(arrayQueue);
    
                if (i % 3 == 2) {
                    arrayQueue.dequeue();
                    System.out.println(arrayQueue);
                }
            }
        }
    }
    

    .end

    展开全文
  • 循环队列详解

    千次阅读 2018-10-07 03:15:51
    前面分析顺序队的时候,我们知道,顺序队存在”假溢出”的问题,这个问题有时会造成很大的内存浪费,循环队列就是为了解决这个问题而提出地一个很巧妙的办法....1. 在循环队列中当队首、队尾指针指向向...
  • 循环队列——队列的顺序表示...1. 在循环队列中当队首、队尾指针指向向量上界(MAX_QUEUE_SIZE-1) 时,其加1 操作的结果是指向向量的下界 0 。而在顺序队列中,说明队已满,若此时采用的是动态顺序链,可以增加申请内存.若是
  • 引用循环队列前,我们需要了解队列是如何线性实现的。    (纠错:上图出队列应该是:x=sq[front++])简单地讲,便是当队列为空时,front = rear = 0,每当插入元素尾指针+1,删除元素是头指针-1。但是,我们会...
  • 线性结构的不多说,是一种操作受限制的...刚开始先看普通队列, 不断的入队,rear往上移动,出队front往上移动,这个队列的实际有效区域两个指针之间,于是随front往上移动的过程front以下的空间就不能利用了,...
  • 什么是队列?  队列就是只能一端插入,而另一端删除的线性表,故队列又称为先进先出队列 ...出队:将对头元素从队列中删除并返回的值 class Queue: """非循环队列""" def __init__(self, size):
  • 1、队列: 队列首指针front = -1; 队列尾指针rear = -1; 队列满的条件:rear == maxSize(队列最大长度)- 1; ...队列空的条件:rear == front;...队列无法重复使用,一旦队首指针...在循环队列中加入了一个空闲空间,...
  • 循环队列 循环队列概念 所谓的循环队列,其实还是一个队列,从外部调用的接口和实际的功能上看和普通的队列...假如向队列中入队11,22,33,44这四个元素,则其存储结构如图所示。 此时若将元素55入队列,则直接尾元

空空如也

空空如也

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

在循环队列中