网站快照怎么更新,工程建设教育网,无锡cms建站,全国企业名录大全话说有很多数据结构都在玩组合拳#xff0c;比如说#xff1a;块状链表#xff0c;块状数组#xff0c;当然还有本篇的双端队列#xff0c;是的#xff0c;它就是栈和队列的组合体。
一、概念
我们知道普通队列是限制级的一端进#xff0c;另一端出的 FIFO 形式#…话说有很多数据结构都在玩组合拳比如说块状链表块状数组当然还有本篇的双端队列是的它就是栈和队列的组合体。
一、概念
我们知道普通队列是限制级的一端进另一端出的 FIFO 形式栈是一端进出的 LIFO 形式而双端队列就没有这样的限制也就是我们可以在队列两端进行插入或者删除操作。
二、编码
2.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.2、队尾入队
刚才也说了双端队列是可以在队列的两端进行插入和删除的要注意的是我们用 head 和 tail 指针的时候tail 指针是指向元素的下一个位置 而 head 指针是指向当前元素所以我们可以从 tail 端 push 数据的时候只要”顺时针“下移一个位置即可。 /// summary/// 队尾入队/// /summary/// param namet/param/// returns/returnspublic 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;}2.3、队尾出队
和队尾入队一样我们只要将 tail 指针”逆时针“下移一个位置当然有一个细节需要注意就是 tail 指针有存在负值的情况毕竟我们是做”–操作“的所以需要 tailmaxSize即
myQueue.tail (--myQueue.tail myQueue.maxSize) % myQueue.maxSize;/// summary/// 队尾出队/// /summary/// param nameedges/param/// param namet/parampublic 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;}2.4、队首入队
从 head 端来说我们 push 数据的时候是 head 指针“逆时针”旋转要注意的是同样要防止负数的产生并且 head 指针是指向当前元素。 /// summary/// 队首入队/// /summary/// param namet/param/// returns/returnspublic 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;}2.5、队首出队
说到这个方法我想大家应该都懂了双端队列的大概流程了这个方法我也不用赘叙了。 /// summary/// 队首出队/// /summary/// param nameedges/param/// param namet/parampublic 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){DoubleQueueint queue new DoubleQueueint();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);}}/// summary/// 双端队列/// /summarypublic class DoubleQueueT{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();/// summary/// 队尾入队/// /summary/// param namet/param/// returns/returnspublic 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;}/// summary/// 队尾出队/// /summary/// param nameedges/param/// param namet/parampublic 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;}/// summary/// 队首入队/// /summary/// param namet/param/// returns/returnspublic 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;}/// summary/// 队首出队/// /summary/// param nameedges/param/// param namet/parampublic 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;}}
