博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
经典算法题每日演练——第十九题 双端队列
阅读量:5840 次
发布时间:2019-06-18

本文共 5371 字,大约阅读时间需要 17 分钟。

     话说大学的时候老师说妹子比工作重要~,工作可以再换,妹子这个。。。所以。。。这两个月也就一直忙着Fall in love,嗨,慢慢调整心态吧,

这篇就选一个简单的数据结构聊一聊,话说有很多数据结构都在玩组合拳,比如说:块状链表,块状数组,当然还有本篇的双端队列,是的,它就是

栈和队列的组合体。

一:概念

     我们知道普通队列是限制级的一端进,另一端出的FIFO形式,栈是一端进出的LIFO形式,而双端队列就没有这样的限制级,也就是我们可以在

队列两端进行插入或者删除操作。

二:编码

1:定义结构体

    通常情况下,队列的内部都是采用数组来实现,而且带有两个指针head和tail来指向数组的区间段,为了充分利用数组空间,我们也会用%来实

现逻辑上的循环数组,如下图。

public class MyQueue    {        public int head;        public int tail;        public int maxSize;        public int size;        public T[] list;        public MyQueue()        {            head = tail = size = 0;            maxSize = 3;            list = new T[maxSize];        }    }

这里有一个注意的细节就是“size字段“,它是为了方便统计队列是否为满或者队列是否为空。

2:队尾入队

    刚才也说了,双端队列是可以在队列的两端进行插入和删除的,要注意的是我们用head和tail指针的时候,tail指针是指向元素的下一个位置,

而head指针是指向当前元素,所以我们可以从tail端push数据的时候只要”顺时针“下移一个位置即可。

///     /// 队尾入队    ///     ///     /// 
public bool Push_Tail(T t) { //判断队列是否已满 if (myQueue.size == myQueue.list.Length) return false; myQueue.list[myQueue.tail] = t; //顺时针旋转 myQueue.tail = (myQueue.tail + 1) % myQueue.maxSize; myQueue.size++; return true; }

3:队尾出队

    和队尾入队一样,我们只要将tail指针”逆时针“下移一个位置,当然有一个细节需要注意,就是tail指针有存在负值的情况,毕竟我们是做”--操作“的,

所以需要tail+maxSize,即:myQueue.tail = (--myQueue.tail + myQueue.maxSize) % myQueue.maxSize;

///     /// 队尾出队    ///     ///     ///     public T Pop_Tail()    {        //判断队列是否已空        if (myQueue.size == 0)            return default(T);        //逆时针旋转(防止负数)        myQueue.tail = (--myQueue.tail + myQueue.maxSize) % myQueue.maxSize;        var temp = myQueue.list[myQueue.tail];        //赋予空值        myQueue.list[myQueue.tail] = default(T);        myQueue.size--;        return temp;    }

4:队首入队

    从head端来说,我们push数据的时候是head指针“逆时针”旋转,要注意的是同样要防止负数的产生,并且head指针是指向当前元素。

///     /// 队首入队    ///     ///     /// 
public bool Push_Head(T t) { //判断队列是否已满 if (myQueue.size == myQueue.list.Length) return false; //逆时针旋转(防止负数产生) myQueue.head = (--myQueue.head + myQueue.maxSize) % myQueue.maxSize; //赋予元素 myQueue.list[myQueue.head] = t; myQueue.size++; return true; }

5:队首出队

    说到这个方法,我想大家应该都懂了双端队列的大概流程了,这个方法我也不用赘叙了。

///     /// 队首出队    ///     ///     ///     public T Pop_Head()    {        //判断队列是否已空        if (myQueue.size == 0)            return default(T);        //获取队首元素        var temp = myQueue.list[myQueue.head];        //原来单位的值赋默认值        myQueue.list[myQueue.head] = default(T);        //顺时针旋转        myQueue.head = (myQueue.head + 1) % myQueue.maxSize;        myQueue.size--;        return temp;    }

从上面的四个方法可以看出:

当我们只使用Push_Tail和Pop_Tail的话,那它就是栈。

当我们只使用Push_Tail和Pop_Head的话,那它就是队列。

最后是全部代码:

using System.Net;using System;using System.IO;using System.Collections.Generic;using System.Text;using System.Drawing;using System.Drawing.Imaging;class Program{    static void Main(string[] args)    {        DoubleQueue
queue = new DoubleQueue
(); queue.Push_Tail(10); queue.Push_Tail(20); queue.Push_Tail(30); queue.Pop_Tail(); queue.Pop_Tail(); queue.Pop_Tail(); queue.Push_Tail(10); queue.Push_Head(20); queue.Push_Head(30); queue.Push_Head(30); queue.Pop_Tail(); queue.Pop_Tail(); queue.Pop_Head(); queue.Push_Head(40); queue.Push_Tail(50); queue.Push_Tail(60); }}///
/// 双端队列/// public class DoubleQueue
{ public class MyQueue { public int head; public int tail; public int maxSize; public int size; public T[] list; public MyQueue() { head = tail = size = 0; maxSize = 3; list = new T[maxSize]; } } MyQueue myQueue = new MyQueue(); ///
/// 队尾入队 /// ///
///
public bool Push_Tail(T t) { //判断队列是否已满 if (myQueue.size == myQueue.list.Length) return false; myQueue.list[myQueue.tail] = t; //顺时针旋转 myQueue.tail = (myQueue.tail + 1) % myQueue.maxSize; myQueue.size++; return true; } ///
/// 队尾出队 /// ///
///
public T Pop_Tail() { //判断队列是否已空 if (myQueue.size == 0) return default(T); //逆时针旋转(防止负数) myQueue.tail = (--myQueue.tail + myQueue.maxSize) % myQueue.maxSize; var temp = myQueue.list[myQueue.tail]; //赋予空值 myQueue.list[myQueue.tail] = default(T); myQueue.size--; return temp; } ///
/// 队首入队 /// ///
///
public bool Push_Head(T t) { //判断队列是否已满 if (myQueue.size == myQueue.list.Length) return false; //逆时针旋转(防止负数产生) myQueue.head = (--myQueue.head + myQueue.maxSize) % myQueue.maxSize; //赋予元素 myQueue.list[myQueue.head] = t; myQueue.size++; return true; } ///
/// 队首出队 /// ///
///
public T Pop_Head() { //判断队列是否已空 if (myQueue.size == 0) return default(T); //获取队首元素 var temp = myQueue.list[myQueue.head]; //原来单位的值赋默认值 myQueue.list[myQueue.head] = default(T); //顺时针旋转 myQueue.head = (myQueue.head + 1) % myQueue.maxSize; myQueue.size--; return temp; }}

转载地址:http://raxcx.baihongyu.com/

你可能感兴趣的文章
netty-当一个客户端连接到来的时候发生了什么
查看>>
PHP_5.3.20 源码编译安装PHP-FPM
查看>>
在51CTO三年年+了,你也来晒晒
查看>>
js控制图片等比例缩放
查看>>
Java高级开发工程师面试考纲
查看>>
FreeMarker表达式
查看>>
Debian9.2 下使用vnstat查看服务器带宽流量统计
查看>>
NGINX + PHP-FPM 502
查看>>
mysql数据备份与恢复
查看>>
Openstack API常用命令
查看>>
OpenSSL漏洞凶猛来袭 慧眼恶意代码监测应对有方
查看>>
C语言 喝汽水问题
查看>>
LINUX中搭建DNS服务器,实现正向、反向以及访问不同DNS解析
查看>>
SCCM2012 R2实战系列之十:解决WDS服务无法启动问题(错误1067:进程意外终止)...
查看>>
ubuntu 下安装 mysql
查看>>
关于k-means聚类算法的matlab实现
查看>>
Git分支2
查看>>
一键安装Gitlab后的备份、迁移与恢复
查看>>
因为本人工作繁忙,精力有限,本博客停止更新。有兴趣的博友可以关注我在CSDN上的主博客...
查看>>
SQL server查看触发器是否被禁用
查看>>