精华内容
下载资源
问答
  • 假定一个单向循环链表来表示队列
  • Round9—循环队列及综合

    千次阅读 2019-10-08 12:33:41
    1-1所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。(F) (1分) 解析:循环队列是一个抽象的数据结构,而单向循环链表和循环数组都是具体的实现方法并不是数据结构的本身。 1-2在数组表示的循环...

    判断题:

    1-1所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。(F) (1分)

    解析:循环队列是一个抽象的数据结构,而单向循环链表和循环数组都是具体的实现方法并不是数据结构的本身。

    1-2在用数组表示的循环队列中,front值一定小于等于rear值。(F) (1分)

    解析由于出队与入队操作front = (front+1)% n,rear = (rear + 1)% n;

    我们只能保证front与rear是在0到n-1之间的,但是我们无法保证front是一直小于等于rear的。

    1-3不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑"溢出"情况。(T) (2分)

    解析:题目当中说明了,在顺序结构上考虑,由于顺序结构我们使用数组实现的。因此,我们需要考虑数组的长度,但是如果我们是用链表这样的链式存储结构,就不需要考虑了。

    选择题:

    2-1若用大小为6的数组来实现循环队列,且当前frontrear的值分别为0和4。当从队列中删除两个元素,再加入两个元素后,frontrear的值分别为多少? (2分)

    • 2和0
    • 2和2
    • 2和4
    • 2和6

    解析:删除元素永远都是front指针移动,也就是永远都是队列的首元素出队列,插入元素永远都是rear指针移动,也就是说元素入队都是插入在队尾。

    那么我们可以根据front = (front+1)% n,rear = (rear + 1)% n来计算操作之后的front与rear的值是多少。

    2-2如果循环队列用大小为m的数组表示,且用队头指针front和队列元素个数size代替一般循环队列中的frontrear指针来表示队列的范围,那么这样的循环队列可以容纳的元素个数最多为: (2分)

    • m-1
    • m
    • m+1
    • 不能确定

    解析:我们前面采用front与rear指针来实现循环队列其中队满的判断是front = (rear+ 1)% n来判断的,因此我们是实际容纳元素的个数就是m-1,但是这里我们用size代替了rear指针,也就是说我们队满可以用size与m的关系来判断。

    因此这里的实际容纳元素的数目就是m。

    2-3如果循环队列用大小为m的数组表示,队头位置为front、队列元素个数为size,那么队尾元素位置rear为: (2分)

    • front+size
    • front+size-1
    • (front+size)%m
    • (front+size-1)%m

    解析:在这里我们要看清楚rear指针到底是指向的哪里,在这里rear指向的是最后一个元素的位置,并不是最后一个元素的后面,也就是这里的rear指针指向的不是插入位置。

    因此rear = (front + size - 1)% m。

    编程题:

    7-1 银行排队问题之单队列多窗口服务 (25 分)

    假设银行有K个窗口提供服务,窗口前设一条黄线,所有顾客按到达时间在黄线后排成一条长龙。当有窗口空闲时,下一位顾客即去该窗口处理事务。当有多个窗口可选择时,假设顾客总是选择编号最小的窗口。

    本题要求输出前来等待服务的N位顾客的平均等待时间、最长等待时间、最后完成时间,并且统计每个窗口服务了多少名顾客。

    输入格式:

    输入第1行给出正整数N(≤1000),为顾客总人数;随后N行,每行给出一位顾客的到达时间T和事务处理时间P,并且假设输入数据已经按到达时间先后排好了顺序;最后一行给出正整数K(≤10),为开设的营业窗口数。这里假设每位顾客事务被处理的最长时间为60分钟。

    输出格式:

    在第一行中输出平均等待时间(输出到小数点后1位)、最长等待时间、最后完成时间,之间用1个空格分隔,行末不能有多余空格。

    在第二行中按编号递增顺序输出每个窗口服务了多少名顾客,数字之间用1个空格分隔,行末不能有多余空格。

    输入样例:

    9
    0 20
    1 15
    1 61
    2 10
    10 5
    10 3
    30 18
    31 25
    31 2
    3
    

    输出样例:

    6.2 17 61
    5 3 1

    AC代码:

     

    #include <bits/stdc++.h>
    using namespace std;
    
    const int maxn = 1000;
    struct Person
    {
        int arrive_time;
        int use_time;
        int wait_time;
        int end_time;
        bool vis;
        Person(int arrive_time, int use_time) : arrive_time(arrive_time), use_time(use_time)
        {
            wait_time = 0;
            vis = false;
        }
    };
    struct Window
    {
        int nums;
        int end_time;
        Window() : nums(0) {}
    };
    bool vis_time[15][maxn * 6];
    int n, k, max_wait, all_time;
    vector<Person> G;
    vector<Window> P;
    
    void solve()
    {
        queue<Person> que;
        for(int now_time = 0; ; now_time++)
        {
            if(que.size() >= n)
                return ;
    
            for(int i = 0; i < k; i++)
            {
                if(vis_time[i][now_time])
                    continue;
                for(int j = 0; j < n; j++)
                {
                    if(G[j].vis)
                        continue;
    
                    if(G[j].arrive_time <= now_time)
                    {
                        P[i].nums++;
                        G[j].wait_time = now_time - G[j].arrive_time;
                        max_wait = max(max_wait, G[j].wait_time);
                        G[j].end_time = now_time + G[j].use_time;
                        G[j].vis = true;
                        for(int time = 0; time < G[j].use_time; time++)
                            vis_time[i][now_time + time] = true;
                        que.push(G[j]);
                        break;
                    }
                    else
                        break;
                }
            }
        }
    }
    
    int main()
    {
        ios::sync_with_stdio(false);
        cin >> n;
        for(int i = 0; i < n; i++)
        {
            int arrive_time, use_time;
            cin >> arrive_time >> use_time;
            if(use_time > 60)
                use_time = 60;
            G.push_back(Person(arrive_time, use_time));
        }
        cin >> k;
        for(int i = 0; i < k; i++)
            P.push_back(Window());
        solve();
        double time = 0;
        for(int i = 0; i < n; all_time = max(all_time, G[i].end_time), i++)
            time += G[i].wait_time;
        cout << fixed << setprecision(1) << time / n << " ";
        cout << max_wait << " " << all_time << endl;
        cout << P[0].nums;
        for(int i = 1; i < k; i++)
            cout << " " << P[i].nums;
        cout << endl;
        return 0;
    }
    

    解析:其实也不是队列,就是大模拟。

    7-2 列车调度 (25 分)

    火车站的列车调度铁轨的结构如下图所示。

    两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在图中有9趟列车,在入口处按照{8,4,2,5,3,9,1,6,7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开,则至少需要多少条平行铁轨用于调度?

    输入格式:

    输入第一行给出一个整数N (2 ≤ N ≤10​5​​),下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。

    输出格式:

    在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。

    输入样例:

    9
    8 4 2 5 3 9 1 6 7
    

    输出样例:

    4
    #include <bits/stdc++.h>
    using namespace std;
    
    const int maxn = 100000 + 5;
    int a[maxn];
    int dp[maxn];
    bool vis[maxn];
    int n;
    
    int main()
    {
    
        cin >> n;
        for(int i = 0; i < n; i++)
            cin >> a[i];
    
        int cnt = 1;
        dp[0] = a[0];
        for(int i = 1; i < n; i++)
        {
            if(a[i] > dp[cnt - 1])
            {
                dp[cnt++] = a[i];
                vis[i] = true;
            }
            else
            {
                int pos = lower_bound(dp, dp + cnt, a[i]) - dp;
                dp[pos] = a[i];
            }
        }
    
        cout << cnt << endl;
        return 0;
    }
    
    

    解析:我们根据贪心的策略,能够分析出实际上的操作跟求LIS的nlogn的算法是一样的。

     

    展开全文
  • 今天带各位回顾一下线性数据结构:数组链表、栈、队列,相信通过下面的文字,你会加深对这几种数据结构的认识。一 数组数组(Array)是一种很常见的数据结构。它是由相同类型的元素(element)的集合所组成,并且被...

    今天带各位回顾一下线性数据结构:数组、链表、栈、队列,相信通过下面的文字,你会加深对这几种数据结构的认识。

    一 数组

    数组(Array) 是一种很常见的数据结构。它是由相同类型的元素(element)的集合所组成,并且被分配一块连续的内存来存储(与链表对比)。利用元素的索引(index)可以计算出该元素对应的存储地址。它的特点是提供随机访问并且容量有限。

    假如数组的长度为 n。
    访问:O(1)//访问特定位置的元素   
    插入:O(n )//最坏的情况发生在插入发生在数组的首部并需要移动所有元素时
    删除:O(n)//最坏的情况发生在删除数组的开头发生并需要移动第一元素后面所有的元素时
    9834e422542879cc753f63836bc6c956.png
    数组

    二 链表

    2.1 链表简介

    链表(LinkedList) 虽然是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储,链表在插入和删除的时候可以达到 O(1) 的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间,而顺序表相应的时间复杂度分别是O(logn) 和O(1)。

    使用链表结构可以克服数组需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但链表不会节省空间,相比于数组会占用更多的空间,因为链表中每个节点存放的还有指向其他节点的指针。链表不具有数组随机读取的优点,但是插入删除元素的时间复杂度为O(1)

    2.2 链表分类

    常见链表分类:

    1. 单链表

    2. 双向链表

    3. 循环链表

    4. 双向循环链表

    假如链表中有n个元素。
    访问:O(n)//访问特定位置的元素
    插入删除:O(1)//必须要要知道插入元素的位置

    2.2.1 单链表

    单链表 单向链表只有一个方向,结点只有一个后继指针 next 指向后面的节点。因此,链表这种数据结构通常在物理内存上是不连续的。我们习惯性地把第一个结点叫作头结点,链表通常有一个不保存任何值的 head 节点(头结点),通过头结点我们可以遍历整个链表。尾结点通常指向null。

    43039405623e0fed2112588b650f9a1b.png
    单链表

    2.2.2 循环链表

    循环链表 其实是一种特殊的单链表,和单链表不同的是循环链表的尾结点不是指向null,而是指向链表的头结点。

    157e6e5f40aab32dc6934d2dc4a08751.png
    循环链表

    2.2.3 双向链表

    双向链表 包含两个指针,一个prev指向前一个节点,一个next指向后一个节点。

    82f5b0ee8239a99c7f8a17fec68a5b31.png
    双向链表

    2.2.4 双向循环链表

    双向循环链表 最后一个节点的 next 指向head,而 head 的prev指向最后一个节点,构成一个环。

    c17c2095d8a389fdd869ea351a63e2ac.png
    双向循环链表

    2.3 数组vs链表

    1. 数组使用的是连续内存空间对CPU的缓存机制友好,链表则相反。

    2. 数组的大小固定,声明之后就要占用所需的连续内存空间。如果声明的数组过小的话,需要再申请一个更大的内存空间,然后将原数组拷贝进去。数组多的情况下,这将是非常耗时的。链表则天然支持动态扩容。

    三 栈

    3.1 栈简介

     (stack)只允许在有序的线性数据集合的一端(称为栈顶 top)进行加入数据(push)和移除数据(pop)。因而按照 后进先出(LIFO, Last In First Out) 的原理运作。在栈中,push 和 pop 的操作都发生在栈顶。 栈常用一维数组或链表来实现,用数组实现的队列叫作 顺序栈 ,用链表实现的队列叫作 链式栈 。

    假设堆栈中有n个元素。
    访问:O(n)//最坏情况 
    插入删除:O(1)//顶端插入和删除元素
    21173a94a4d4f19e0fac116d286eb31f.png

    3.2 栈的常见应用常见应用场景

    3.2.1 实现浏览器的回退和前进功能

    我们只需要使用两个栈(Stack1和Stack2)和就能实现这个功能。比如你按顺序查看了 1,2,3,4 这四个页面,我们依次把 1,2,3,4 这四个页面压入 Stack1 中。当你想回头看2这个页面的时候,你点击回退按钮,我们依次把4,3这两个页面从Stack1 弹出,然后压入 Stack2 中。假如你又想回到页面3,你点击前进按钮,我们将3页面从Stack2 弹出,然后压入到 Stack1 中。示例图如下:

    1e122eb0d30ab85f4006cf858d272a64.png
    栈实现浏览器倒退和前进

    3.2.2 检查符号是否成对出现

    给定一个只包括 '('')''{''}''['']' 的字符串,判断该字符串是否有效。

    有效字符串需满足:

    1. 左括号必须用相同类型的右括号闭合。

    2. 左括号必须以正确的顺序闭合。

    比如 "()"、"()[]{}"、"{[]}" 都是有效字符串,而 "(]" 、"([)]" 则不是。

    这个问题实际是Leetcode的一道题目,我们可以利用栈 Stack 来解决这个问题。

    1. 首先我们将括号间的对应规则存放在 Map 中,这一点应该毋容置疑;

    2. 创建一个栈。遍历字符串,如果字符是左括号就直接加入stack中,否则将stack的栈顶元素与这个括号做比较,如果不相等就直接返回false。遍历结束,如果stack为空,返回 true

    public boolean isValid(String s){

    3.2.3 反转字符串

    将字符串中的每个字符先入栈再出栈就可以了。

    3.2.4 维护函数调用

    最后一个被调用的函数必须先完成执行,符合栈的 后进先出(LIFO, Last In First Out)特性。

    四 队列

    4.1 队列简介

    队列 是 先进先出( FIFO,First In, First Out) 的线性表。在具体应用中通常用链表或者数组来实现,用数组实现的队列叫作 顺序队列 ,用链表实现的队列叫作 链式队列 。队列只允许在后端(rear)进行插入操作也就是 入队 enqueue,在前端(front)进行删除操作也就是出队 dequeue

    队列的操作方式和堆栈类似,唯一的区别在于队列只允许新数据在后端进行添加。

    假设队列中有n个元素。
    访问:O(n)//最坏情况
    插入删除:O(1)//后端插入前端删除元素
    fafbfe7a43b26d841ad8ccfb79ee7814.png
    队列

    4.2 队列分类

    4.2.1 单队列

    单队列就是常见的队列, 每次添加元素时,都是添加到队尾。单队列又分为 顺序队列(数组实现) 和 链式队列(链表实现)

    顺序队列存在“假溢出”的问题也就是明明有位置却不能添加的情况。

    假设下图是一个顺序队列,我们将前两个元素1,2 出队,并入队两个元素7,8。当进行入队、出队操作的时候,front和 rear 都会持续往后移动,当 rear 移动到最后的时候,我们无法再往队列中添加数据,即使数组中还有空余空间,这种现象就是 ”假溢出“ 。除了假溢出问题之外,如下图所示,当添加元素8的时候,rear 指针移动到数组之外(越界)。

    为了避免当只有一个元素的时候,队头和队尾重合使处理变得麻烦,所以引入两个指针,front 指针指向对头元素,rear 指针指向队列最后一个元素的下一个位置,这样当 front 等于 rear 时,此队列不是还剩一个元素,而是空队列。——From 《大话数据结构》

    085f72ad1b2f08cd32a0bb5b4274b9ee.png
    顺序队列假溢出

    4.2.2 循环队列

    循环队列可以解决顺序队列的假溢出和越界问题。解决办法就是:从头开始,这样也就会形成头尾相接的循环,这也就是循环队列名字的由来。

    还是用上面的图,我们将 rear 指针指向数组下标为 0 的位置就不会有越界问题了。当我们再向队列中添加元素的时候, rear 向后移动。

    295a0c0c0ea9b2e5cf68682fa479ec0e.png
    循环队列

    顺序队列中,我们说 front==rear 的时候队列为空,循环队列中则不一样,也可能为满,如上图所示。解决办法有两种:

    1. 可以设置一个标志变量 flag,当 front==rear 并且 flag=0 的时候队列为空,当front==rear 并且 flag=1 的时候队列为满。

    2. 队列为空的时候就是 front==rear ,队列满的时候,我们保证数组还有一个空闲的位置,rear 就指向这个空闲位置,如下图所示,那么现在判断队列是否为满的条件就是: (rear+1) % QueueSize= front 。

    55da40a5ecf4d59afbd0798852f8d9ab.png
    循环队列-队满

    常见应用场景

    • 阻塞队列: 阻塞队列可以看成在队列基础上加了阻塞操作的队列。当队列为空的时候,出队操作阻塞,当队列满的时候,入队操作阻塞。使用阻塞队列我们可以很容易实现“生产者 - 消费者“模型。

    • 线程池中的请求/任务队列: 线程池中没有空闲线程时,新的任务请求线程资源时,线程池该如何处理呢?答案是将这些请求放在队列中,当有空闲线程的时候,会循环中反复从队列中获取任务来执行。队列分为无界队列(基于链表)和有界队列(基于数组)。无界队列的特点就是可以一直入列,除非系统资源耗尽,比如 :FixedThreadPool 使用无界队列 LinkedBlockingQueue。但是有界队列就不一样了,当队列满的话后面再有任务/请求就会拒绝,在 Java 中的体现就是会抛出java.util.concurrent.RejectedExecutionException 异常。

    • linux内核进程队列(按优先级排队)

    • 实现生活中的派对,播放器上的播放列表;

    • 消息队列

    • 等等……

    参考

    • https://www.geeksforgeeks.org/overview-of-data-structures-set-1-linear-data-structures/

    • 《大话数据结构》

    推荐阅读

    推荐20个5月最热门的Java开源项目

    15个经典的Spring面试常见问题

    面试官:“谈谈Spring中都用到了那些设计模式?”。

    不就是个短信登录API嘛,有这么复杂吗?

    漫画的方式带你了解重构!原来重构如此简单!!

    后端开发实践系列——Spring Boot项目模板

    盘点阿里巴巴 15 款开发者工具

    蚂蚁金服2019实习生面经总结(已拿口头offer)

    记一次蚂蚁金服的面试经历

    Java学习必备书籍推荐终极版!

    我觉得技术人员该有的提问方式

    Java 8 新特性最佳指南

    做公众号这一年的经历和一件“大事”(2018-03-10)

    盘点一下Github上开源的Java面试/学习相关的仓库,看完弄懂薪资至少增加10k( 2018-12-24)

    可能是一份最适合你的后端面试指南(部分内容前端同样适用)

    8d881bb87d574aea16382135874e077a.png

    欢迎关注b958accf1552b4b333c39f03eabbddf7.png点个再看7651e36a5a1bf94518af2ca4b0e1dd24.png

    展开全文
  • 数据结构作业9—队列(判断题)

    千次阅读 2018-12-20 16:50:22
    1-1所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。 (1分) T F 作者: DS课程组 单位: 浙江大学 1-2不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑"溢出"情况。 (2分) T ...

    1-1所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。 (1分)

    • T
    • F

    作者: DS课程组
    单位: 浙江大学

    1-2不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑"溢出"情况。 (2分)

    • T
    • F

    作者: 林华
    单位: 广东外语外贸大学

    1-3在用数组表示的循环队列中,front值一定小于等于rear值。 (1分)

    • T
    • F

    作者: DS课程组
    单位: 浙江大学

    展开全文
  • 队列是一种线性的数据结构【线性数据结构:数组、栈、队列】 相比数组队列对应的数据操作是数组的子集。 只能从一端(队尾)添加元素,只能从另一端(队首)取出元素。   数组队列 代码实现 Array数组类 ...

    什么是队列?

    队列是一种线性的数据结构【线性数据结构:数组、栈、队列】

    相比数组,队列对应的数据操作是数组的子集。

    只能从一端(队尾)添加元素,只能从另一端(队首)取出元素。

     

    数组队列

    代码实现

    Array数组类

    package cn.itcats.queue;
    
    public class Array<E> {
        private E[] data;
        private int size;
    
        public Array(int capacity) {
            data =(E[]) new Object[capacity];
            size = 0;
        }
    
        public Array() {
            //空参数构造默认的capacity为10
            this(10);
        }
    
        //获取数组元素中元素个数
        public int getSize() {
            return this.size;
        }
    
        //获得数组容量
        public int getCapacity() {
            return data.length;
        }
    
        //判断数组是否为空
        public boolean isEmpty() {
            return size == 0;
        }
    
        //向数组尾部添加元素
        public void addLast(E e) {
            add(size, e);
        }
    
        //向数组头部添加元素
        public void addFirst(E e) {
            add(0, e);
        }
    
        //向数组中index索引处插入某个元素
        public void add(int index, E e) {
            //检查数组中是否能容纳新的元素
            if (size == data.length)
                System.out.println("数组需要扩容");
                resize(data.length * 2);
            if (index < 0 || index > size)
                throw new IllegalArgumentException("index非法");
            //移动元素
            for (int i = size - 1; i >= index; i--) {
                //后一个索引赋上前一个索引的元素,即每一个元素都向后挪了一个位置
                data[i + 1] = data[i];
            }
            data[index] = e;
            size++;
        }
    
        //获取数组中的值
        E get(int index) {
            if (index < 0 || index >= size)
                throw new IllegalArgumentException("index非法");
            return data[index];
        }
    
        //获取数组中的值
        E getLast() {
            return get(size - 1);
        }
    
        //获取数组中的值
        E getFirst() {
            return get(0);
        }
    
        //更新数组的值
        E update(int index, E e) {
            E oldValue = get(index);
            data[index] = e;
            return oldValue;
        }
    
        //数组中是否含有某元素,有返回true,无返回false
        public boolean contains(E e) {
            for (int i = 0; i < size; i++) {
                if (data[i].equals(e))
                    return true;
            }
            return false;
        }
    
        //查找数组中的某个元素,找到返回索引,找不到返回-1
        public int find(E e) {
            for (int i = 0; i < size; i++) {
                if (data[i].equals(e)) {
                    return i;
                }
            }
            return -1;
        }
    
        //删除数组中某个元素
        public E remove(int index) {
            if (index < 0 || index >= size) {
                throw new IllegalArgumentException("index非法");
            }
            E ret = data[index];
            for (int i = index + 1; i < size; i++) {
                data[i - 1] = data[i];
            }
            size--;
            data[size] = null;
            if(size == data.length / 4 && data.length / 2 != 0 )
                resize(data.length /2);
            return ret;
        }
    
        public E removeFirst() {
            return remove(0);
        }
    
        public E removeLast() {
            return remove(size - 1);
        }
    
        //删除指定元素,如果有则删除,删除成功返回true,删除失败返回false
        public boolean removeElement(E e) {
            int index = find(e);
            if(index != -1){
                remove(index);
                return true;
            }
            return false;
        }
    
        //实现动态数组,动态扩容 size==data.lenngth 扩容2倍 和 缩容 size == data.length / 2
        private void resize(int newCapacity){
            //创建一个新的数组
            E[] newData = (E[]) new Object[newCapacity];
            //把原来的元素迁移到新的数组中
            for(int i = 0 ; i < size ; i++){
                newData[i] = data[i];
            }
            data = newData;
        }
    
        //打印数组中的元素
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
            //显示[1,2,3,4,5]
            sb.append("[");
            for (int i = 0; i < size; i++) {
                sb.append(data[i]);
                if (i != size - 1) {
                    sb.append(", ");
                }
            }
            sb.append("]");
            return sb.toString();
        }
    
    
    }
    

     

    Queue接口

    package cn.itcats.queue;
    
    public interface Queue<E> {
        //入队操作
        void enqueue(E e);
        //出队操作
        E dequeue();
        //获取队首元素
        E getFront();
        //获取队列中元素个数
        int getSize();
        //判断队列是否为空
        boolean isEmpty();
    }
    

     

    基于数组实现的Queue

    package cn.itcats.queue;
    
    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 void enqueue(E e) {
            array.addLast(e);
        }
    
        @Override
        public E dequeue() {
            return array.removeFirst();
        }
    
        @Override
        public E getFront() {
            return array.getFirst();
        }
    
        @Override
        public int getSize(){
            return array.getSize();
        }
    
        @Override
        public boolean isEmpty() {
            return array.isEmpty();
        }
    
        public int getCapacity(){
            return array.getCapacity();
        }
    
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append(String.format("Queue: "));
            sb.append("front [");
            for (int i = 0; i < array.getSize(); i++) {
                sb.append(array.get(i));
                if (i != array.getSize() - 1) {
                    sb.append(", ");
                }
            }
            sb.append("] tail");
            return sb.toString();
        }
    
        //测试
        public static void main(String[] args) {
            ArrayQueue<Integer> queue = new ArrayQueue<>();
            for(int i = 0 ; i < 10 ;i ++){
                queue.enqueue(i);
                System.out.println("i:"+i +" "+queue);
    
                if(i % 3 == 2){
                    queue.dequeue();
                    System.out.println("i:"+i +" "+queue);
                }
            }
        }
    
    }
    

    使用数组实现队列的复杂度分析:

    可以看到,因为每次出队都调用removeFirst()方法,时间复杂度O(n),那么有没有什么方法可以实现入队和出队时间复杂度都是O(1)呢?答案是有的,下面我们就来说说循环队列

     

    循环队列

    由于数组队列的出队时间复杂度都为O(n),原因是每次出队时都需要移动元素进行赋值操作,那么循环队列便产生了。

    循环队列内部维护了两个指针,front和tail。

    1、在初始化时,front和tail都指向索引为0的位置,所以当front==tail时,队列为空

    2、每入队一个元素,tail++,每出队一个元素,front++。

    3、到tail++到末尾时,若开头还有可利用的空间,则7之后的索引其实是0。  index = (7+1) % capacitySize == 0

    3、如下图所示,如果在索引1处放置一个元素,tail++,此时tail==front,但此时队列并不为空,这并不是我们想看见的,所以数组中需要浪费一个索引空间当(tail+1) % capacity ==front时,队列为满,所以索引1不放元素。有些人可能疑问为什么不是tail+1 == front呢?当tail==7时,再加入一个元素,靠的就是取模运算把下一个tail放在索引0位置的,当tail为0,front为7时,队列也是满的,而7+1 != front,不能判断队列是满的,所以需要(tail+1) % capacity ==front,判断队列为满。

     

    代码实现:

    package cn.itcats.queue;
    
    /**
     * 循环队列   基于数组
     * @param <E>
     */
    public class LoopQueue<E> implements Queue<E> {
    
        private E[] data;
        private int front , tail;
        private int size;
    
        public LoopQueue(int capacity){
            //因为循环队列我们有意识的浪费一个空间,所以长度+1
            data = (E[]) new Object[capacity + 1];
            front = 0;
            tail = 0;
            size = 0;
        }
        public LoopQueue(){
            this(10);
        }
    
        //入队操作
        @Override
        public void enqueue(E e) {
            //入队之前判断队列是否为满
            if(front == (tail+1) % data.length){
                //队列满了,扩容
                resize(getCapacity() * 2);
            }
            data[tail] = e;
            tail = (tail + 1) % data.length;
            size++;
        }
    
        //出队操作
        @Override
        public E dequeue() {
            //队列为空
            if(isEmpty())
                throw new IllegalArgumentException("队列为空,无法出队");
            //队列不为空,出队元素
            E e = data[front];
            //出队后把元素置空
            data[front] = null;
            front = (front + 1) % data.length;
            size -- ;
    
            //若出队到一定数量时,动态缩小容量
            if(size == getCapacity() / 4 && getCapacity() / 2 != 0 ){
                resize(getCapacity() / 2);
            }
            return e;
        }
    
        //扩容过程
        private void resize(int newCapacity){
            //构建一个新的数组   长度为原来可用空间的两倍
            E[] newData = (E[]) new Object[newCapacity + 1];
            //迁移数组
            for(int i = 0 ; i < size ; i++){
                //把原来front位置的元素依次迁移到新数组0开始的位置,存在偏移量front
                newData[i] = data[(i+front) % data.length];
            }
            //改变引用
            data = newData;
            //front和tail归位
            front = 0 ;
            tail = size;
        }
    
        //查看队首元素,但不出队
        @Override
        public E getFront() {
            //队列为空
            if(isEmpty())
                throw new IllegalArgumentException("队列为空,无法查看队首元素");
            return data[front];
        }
    
        @Override
        public int getSize() {
            return size;
        }
    
        @Override
        public boolean isEmpty() {
            return front == tail;
        }
    
        public int getCapacity(){
            return data.length - 1;
        }
    
        //打印数组中的元素
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append(String.format("LoopQueue: size = %d , capacity = %d\n", size, getCapacity()));
            //显示[1,2,3,4,5]
            sb.append("front [");
            for (int i = front; i != tail; i = (i+1) % data.length) {
                sb.append(data[i]);
                //如果当前索引不是最后一个元素
                if ( (i+1) % data.length != tail) {
                    sb.append(", ");
                }
            }
            sb.append("] tail");
            return sb.toString();
        }
    
        //测试方法
        public static void main(String[] args) {
            LoopQueue<Integer> queue = new LoopQueue<>();
            for(int i = 0 ; i < 10 ;i ++){
                queue.enqueue(i);
                System.out.println("i:"+i +" "+queue);
    
                if(i % 3 == 2){
                    queue.dequeue();
                    System.out.println("i:"+i +" "+queue);
                }
            }
        }
    }
    

     

    数组队列与循环队列的比较

    1、循环队列相比数组队列底层都是基于数组,但循环队列编码更复杂一些,它引入了front和tail指针。

    2、数组队列出队时间复杂度为O(n),而循环队列出队时间复杂度为O(1)。【均摊复杂度】,因为可能触发缩容操作。

     

    为此,我们可以对二者进行性能测试。

    package cn.itcats.queue;
    
    import java.util.Random;
    
    public class SpeedTest {
    
    
        //模拟执行count次入队和出队所需时间,单位:  s 秒
        public static double speedTest(Queue<Integer> queue, int count){
            long startTime = System.nanoTime();
            Random random = new Random();
            for(int i = 0 ; i < count ; i++)
                queue.enqueue(random.nextInt(Integer.MAX_VALUE));
            for(int i = 0 ; i < count ; i++)
                queue.dequeue();
            long endTime = System.nanoTime();
            return (endTime - startTime) /1000000000.0 ;
        }
    
        public static void main(String[] args) {
            //进行入队和出队的次数
            int count = 2000000;
            //使用数组队列ArrayQueue
            Queue arrayQueue = new ArrayQueue();
            System.out.println("ArrayQueue数组队列执行的时间:  "+speedTest(arrayQueue,count)+"  s");
            //使用循环队列LoopQueue
            Queue loopQueue = new LoopQueue();
            System.out.println("LoopQueue循环队列执行的时间:  " + speedTest(loopQueue,count)+"  s");
        }
    }
    

    发现loopQueue要比arrayQueue快上百倍。

     

    基于链表实现队列

    因为我设计的链表为单向链表,若在tail删除元素不容易获得tail的前一个元素,故在head端进行删除操作

    package cn.itcats.queue;
    
    import cn.itcats.linkedlist.LinkedList;
    
    public class LinkedListQueue<E> implements Queue<E>{
        //创建内部类Node
        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 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 retNode = head;
            head = head.next;
            retNode.next = null;
            if(head == null){
                tail = null;
            }
            size -- ;
            return retNode.e;
        }
    
        @Override
        public E getFront() {
            if(isEmpty())
                throw new IllegalArgumentException("队列为空");
            return head.e;
        }
    
        @Override
        public int getSize() {
            return size;
        }
    
        @Override
        public boolean isEmpty() {
            return size == 0;
        }
    
        @Override
        public String toString(){
            StringBuilder sb = new StringBuilder("Queue: front ");
            for(Node cur = head; cur != null ; cur = cur.next)
                sb.append(cur+" -->");
            sb.append("NULL tail");
            return sb.toString();
        }
    
        //测试
        public static void main(String[] args) {
            LinkedListQueue<Integer> queue = new LinkedListQueue<>();
            for(int i = 0 ; i < 10 ;i ++){
                queue.enqueue(i);
                System.out.println(queue);
    
                if(i % 3 == 2){
                    queue.dequeue();
                    System.out.println(queue);
                }
            }
        }
    
    }
    

     

     

     

     

    展开全文
  • 数组队列及循环队列

    2019-10-03 16:02:53
    java数据结构之----数组队列及循环队列 数据结构与算法学习的第二篇 什么时候需要用到队列 队列在实际开发过程中运用的非常广泛,由于我也是学习基础,还没有开发过什么项目,所以用到时候就知道了 什么是队列 ...
  • 1、队列 特点:先进先出 基于数组的实现: public class MyQueue { private int[] elements; public MyQueue() { elements = new int[0]; } //入队列 public void add(int data) { int...
  • 数据结构——循环队列PTA习题

    千次阅读 2020-12-17 23:39:58
    所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。 错 2 在数组表示的循环队列中,front值一定小于等于rear值。 错 3 为解决计算机主机与打印机之间速度不匹配问题,通常设置一个打印数据缓
  • 在之前更新稀疏数组,单双链表,循环链表(约瑟夫环)单向队列后,这次代码实现简单的一维数组完成队列的基本操作,希望对大家有所帮助。在之后持续更新java数据结构。 队列 先进先出 代码功能 1.增加数据 2.取出...
  • 数据结构之数组链表、栈和队列

    千次阅读 2020-08-01 14:30:51
    1.数组 1.1:概念 数组是一种线性表数据结构,它一组连续的内存空间,来存储一组具有相同类型的数据。这里我们要抽取出三个跟数组相关的关键词...所谓的数组的逻辑结构的是我们可以什么的表示方式来描述数组
  • bingqilin.inQueue(88) bingqilin.outQueue() bingqilin.print() 循环队列 循环队列的一个例子就是击鼓传花游戏(Hot Potato)。在这个游戏中,孩子们围成一个圆圈,把花尽快地传递给旁边的人。某一时刻传花停止,...
  • 数据结构算法的关系 ➢数据data结 构(structure)是...线性链表和非线性链表 数据结构包括:线性结构非线性结构。 线性结构 1)线性结构作为最常用的数据结构,其特点是数据元素之间存在- -对- - 的线性关系(a[0]=3
  • /* 使用哨兵 */ /* head指向应该插入的位置,若队列满则指向哨兵 */ /* end指向队列尾,若队列空则指向head*/ int g_queue[MAX_QUEUE + 1] = {0}; unsigned int g_queueHead = 1; unsigned int g_guard = 0; ...
  • 本篇博客所涉及到的代码,均已...本篇博文,将通过数组,单向循环链表两种方式,使用Java实现队列, 帮助大家进一步了解队列这种数据结构 本篇博客要点如下: 队列 基本概念 存储结构 顺序存储结构 链式存储结构 使...
  • 队列是一个有序列表,可以由数组或者链表实现 数据先入后出
  • 在并发多线程之Lock及ReentrantLock源码剖析中了解了独占锁的实现ReentrantLock及Condition的原理和使用,接下来就来了解一下基于ReentrantLockCondition实现的阻塞队列,本篇主要讲解的是数组和链表实现阻塞队列...
  • 文章目录线性结构:非线性结构:稀疏数组和队列: 数据结构包括线性结构非线性结构。 线性结构: ...(4)线性结构常见的有:数组队列链表和栈。 非线性结构: 非线性结构包括:二维数组、多维数组,广
  • 第三章 循环队列及线性结构综合

    千次阅读 2018-10-11 18:01:32
    所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。 (1分)  F F:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。这种循环队列可以...
  • 说明 相比Linux内核链表宿主结构可有多个链表结构的优点,本函数集侧重封装性易用性,而灵活性效率有所降低. 可基于该函数集方便地构造栈或队列集. 本函数集暂未考虑并发保护. 一 概念 链表是一种物理存储单元上非...
  • 链表的基础内容在上篇已经介绍完了,现在介绍链栈的内容,栈的先进后出的特点我就不再赘述了。在介绍顺序表实现栈结构的时候,已经对栈进行了一个完整的介绍,关于结点去实现一个栈结构在Java基础的文章中也已经...
  • // 循环队列#include #include "SeqQue.h"// 循环队列的基本运算/*const int maxsize = 20;typedef struct cycque{int data[maxsize];int front, rear;}CycQue;*/// 1. 初始化void InitQueue(CycQue CQ){CQ.front = ...
  • 数组和链表都是线性存储结构的基础,栈和队列都是线性存储结构的应用~本文主要讲解单链表的基础知识点,做一个简单的入门~如果有错的地方请指正二、回顾与知新说起链表,我们先提一下数组吧,跟数组比较一下就很...
  • 博主最近换了家新公司,刚进去很是清闲,IT这行业发展太迅速,没事干就得学习,不断学习,看过了许多...一 数组实现栈结构 public class MyStack { private long[] a; private int size;//栈数组大小 private ...
  • Python:栈和队列的 python 列表实现中可以看出链表是存在一定问题的: 由于动态数组,底层的数组长度可能会超过实际存储元素的个数,造成空间上的浪费。 我们 append 的平均时间复杂度是 O(1),但是这是摊销的...
  • 单向链表尾插法头插法分别实现队列和

    千次阅读 多人点赞 2021-01-16 15:37:15
      使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间
  • 很多现在语言都比较灵活,提供了...单向链表链表是一组结点组成的集合,每个结点都包含两部分:存储数据元素的数据域存储下一个结点的指针域。在物理存储上非连续,因此在插入删除时效率更高。数据结构查找插入...
  • 数组 数组(Array)是一种很常见的数据结构。它是由相同类型的元素(element)的集合所组成,并且被分配一块连续的内存来存储(与链表对比)。利用元素的索引(index)可以计算出该元素对应的存储地址。它的特点...
  • 循环队列

    2020-05-19 17:13:31
    循环队列是一种特殊的队列,普通队列普遍使用单向链表来表示,所以整个队列在逻辑结构上是一条链,而循环队列用数组来进行表示的,而且其逻辑结构上表示为一个环型结构。 逻辑结构 首先我们看一下循环队列的逻辑...
  • 原创: SnailClimb JavaGuide今天带各位回顾一下线性数据结构:数组链表、栈、队列,相信通过下面的文字,你会加深对这几种数据结构的认识。一 数组数组(Array) 是一种很常见的数据结构。它是由相同类型的元素...
  • 数据结构部分,复习栈,队列数组链表和红黑树,参考博客资料学习后记录到这里方便以后查看,感谢被引用的博主。 栈 栈(stack)又称为堆栈,是线性表,它只能从栈顶进入取出元素,有先进后出,后进先出(LIFO...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,983
精华内容 5,593
关键字:

循环队列是指用单向循环链表和循环数组