首页 / 软件开发 / 数据结构与算法 / 双端队列算法练习题

双端队列算法练习题2013-05-24 cnblogs 一线码农话说大学的时候老师说妹子比工作重要~，工作可以再换，妹子这个。。。所以。。。这两个月也就 一直忙着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数据的时候只要”顺时针“下移一个位置即可。

/// <summary>/// 队尾入队/// </summary>/// <param name="t"></param>/// <returns></returns>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;}