# 数据结构C#版笔记--队列(Quene)

```namespace 栈与队列
{
public interface IQuene<T>
{
/// <summary>
/// 取得队列实际元素的个数
/// </summary>
/// <returns></returns>
public int Count();

/// <summary>
/// 判断队列是否为空
/// </summary>
/// <returns></returns>
public bool IsEmpty();

/// <summary>
/// 清空队列
/// </summary>
public void Clear();

/// <summary>
/// 入队（即向队列尾部添加一个元素）
/// </summary>
/// <param name="item"></param>
public void Enquene(T item);

/// <summary>
/// 出队(即从队列头部删除一个元素)
/// </summary>
/// <returns></returns>
public T Dequene();

/// <summary>
/// 取得队列头部第一元素
/// </summary>
/// <returns></returns>
public T Peek();
}
}```

```using System;
using System.Text;

namespace 栈与队列
{
/// <summary>
/// 循环顺序队列
/// </summary>
/// <typeparam name="T"></typeparam>
public class CSeqQueue<T>:IQueue<T>
{
private int maxsize;
private T[] data;
private int front;
private int rear;

public CSeqQueue(int size)
{
data = new T[size];
maxsize = size;
front = rear = -1;
}

public int Count()
{
if (rear > front)
{
return rear - front;
}
else
{
return (rear - front + maxsize) % maxsize;
}
}

public void Clear()
{
front = rear = -1;
}

public bool IsEmpty()
{
return front == rear;
}

public bool IsFull()
{
if (front != -1) //如果已经有元素出队过
{
return (rear + 1) % maxsize == front;//为了区分与IsEmpty的区别，有元素出队过以后，就只有浪费一个位置来保持逻辑正确性.
}
else
{
return rear == maxsize - 1;
}
}

public void Enqueue(T item)
{
if (IsFull())
{
Console.WriteLine("Queue is full");
return;
}
if (rear == maxsize - 1) //如果rear到头了，则循环重来（即解决伪满问题）
{
rear = 0;
}
else
{
rear++;
}
data[rear] = item;
}

public T Dequeue()
{
if (IsEmpty())
{
Console.WriteLine("Queue is empty");
return default(T);
}
if (front == maxsize - 1) //如果front到头了，则重新置0
{
front = 0;
}
else
{
front++;
}
return data[front];
}

public T Peek()
{
if (IsEmpty())
{
Console.WriteLine("Queue is empty!");
return default(T);
}
return data[(front + 1) % maxsize];
}

public override string ToString()
{
if (IsEmpty()) { return "queue is empty."; }

StringBuilder sb = new StringBuilder();

if (rear > front)
{
for (int i = front + 1; i <= rear; i++)
{
sb.Append(this.data[i].ToString() + ",");
}
}
else
{
for (int i = front + 1; i < maxsize; i++)
{
sb.Append(this.data[i].ToString() + ",");
}

for (int i = 0; i <= rear; i++)
{
sb.Append(this.data[i].ToString() + ",");
}
}
return "front = " + this.front + " \t rear = " + this.rear + "\t count = " + this.Count() + "\t data = " +  sb.ToString().Trim(',');
}
}
}```

```            CSeqQueue<int> queue = new CSeqQueue<int>(5);
queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3);
queue.Enqueue(4);
Console.WriteLine(queue);//front = -1       rear = 3        count = 4       data = 1,2,3,4
queue.Dequeue();
Console.WriteLine(queue);//front = 0        rear = 3        count = 3       data = 2,3,4
queue.Dequeue();
Console.WriteLine(queue);//front = 1        rear = 3        count = 2       data = 3,4
queue.Enqueue(5);
Console.WriteLine(queue);//front = 1        rear = 4        count = 3       data = 3,4,5
queue.Enqueue(6);
Console.WriteLine(queue);//front = 1        rear = 0        count = 4       data = 3,4,5,6
queue.Enqueue(7);        //Queue is full
Console.WriteLine(queue);//front = 1        rear = 0        count = 4       data = 3,4,5,6
queue.Dequeue();
queue.Enqueue(7);
Console.WriteLine(queue);//front = 2        rear = 1        count = 4       data = 4,5,6,7

queue.Clear();
Console.WriteLine(queue);//queue is empty.

queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3);
queue.Enqueue(4);
Console.WriteLine(queue);//front = -1       rear = 3        count = 4       data = 1,2,3,4
queue.Enqueue(5);
Console.WriteLine(queue);//front = -1       rear = 4        count = 5       data = 1,2,3,4,5
queue.Enqueue(6);        //Queue is full
Console.WriteLine(queue);//front = -1       rear = 4        count = 5       data = 1,2,3,4,5
queue.Dequeue();
queue.Dequeue();
queue.Dequeue();
queue.Dequeue();
Console.WriteLine(queue);//front = 3        rear = 4        count = 1       data = 5
queue.Dequeue();
Console.WriteLine(queue);//queue is empty.
queue.Enqueue(0);
queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3);
queue.Enqueue(4);        //Queue is full
Console.WriteLine(queue);//front = 4        rear = 3        count = 4       data = 0,1,2,3
Console.WriteLine(queue.Peek());//0
queue.Dequeue();
Console.WriteLine(queue);//front = 0        rear = 3        count = 3       data = 1,2,3
queue.Dequeue();
Console.WriteLine(queue);//front = 1        rear = 3        count = 2       data = 2,3
queue.Dequeue();
Console.WriteLine(queue);//front = 2        rear = 3        count = 1       data = 3
queue.Dequeue();
Console.WriteLine(queue);//queue is empty.
queue.Enqueue(9);
Console.WriteLine(queue);//front = 3        rear = 4        count = 1       data = 9
Console.ReadLine();```

```namespace 栈与队列
{
public class Node<T>
{
private T data;

private Node<T> next;

public Node(T data, Node<T> next)
{
this.data = data;
this.next = next;
}

public Node(Node<T> next)
{
this.next = next;
this.data = default(T);

}

public Node(T data)
{
this.data = data;
this.next = null;
}

public Node()
{
this.data = default(T);
this.next = null;
}

public T Data {
get { return this.data; }
set { this.data = value; }
}

public Node<T> Next
{
get { return next; }
set { next = value; }
}
}
}```

```using System;
using System.Text;

namespace 栈与队列
{
public class LinkQueue:IQueue
{
private Node front;//队列头
private Node rear;//队列尾
private int num;//队列元素个数

///
/// 构造器
///
public LinkQueue()
{
//初始时front,rear置为null，num置0
front = rear = null;
num = 0;
}

public int Count()
{
return this.num;
}

public void Clear()
{
front = rear = null;
num = 0;
}

public bool IsEmpty()
{
return (front == rear && num == 0);
}

//入队
public void Enqueue(T item)
{
Node q = new Node(item);

if (rear == null)//第一个元素入列时
{
front = rear = q;
}
else
{
//把新元素挂到链尾
rear.Next = q;
//修正rear指向为最后一个元素
rear = q;
}
//元素总数+1
num++;
}

//出队
public T Dequeue()
{
if (IsEmpty())
{
Console.WriteLine("Queue is empty!");
return default(T);
}

//取链首元素
Node p = front;

//链头指向后移一位
front = front.Next;

//如果此时链表为空，则同步修正rear
if (front == null)
{
rear = null;
}

num--;//个数-1

return p.Data;
}

public T Peek()
{
if (IsEmpty())
{
Console.WriteLine("Queue is empty!");
return default(T);
}

return front.Data;
}

public override string ToString()
{
if (IsEmpty()) {
Console.WriteLine("Queue is empty!");
}

StringBuilder sb = new StringBuilder();

Node node = front;

sb.Append(node.Data.ToString());

while (node.Next!=null)
{
sb.Append("," + node.Next.Data.ToString());
node = node.Next;
}

return sb.ToString().Trim(',');
}
}
}```

0 条评论

• ### 温故而知新:设计模式之工厂模式(Factory)

工厂模式：个人理解为主要用于创建"同一系列"的N个对象实例。(注意这里"同一系列"指这一系列对象均继承于某一个抽象类或均实现了某一个接口) 举例：(仍然来自李建...

• ### 温故而知新:设计模式之抽象工厂(AbstractFactory)

抽象工厂主要用来解决多个系列的对象实例问题。 问题的应用场景(来源于李建忠老师的webcast讲座)： 如果有一款游戏，里面有"道路,房屋，隧道，丛林"这四类基...

• ### 温故而知新:设计模式之Builder

Builder模式主要用于以下场景: 需要创建一个较复杂的大对象实例，并且构成该对象的子对象可能经常会发生变化，但是组成大对象的算法却相对稳定。 比如：我们做b...

• ### Enterprise Library深入解析与灵活应用（9）：个人觉得比较严重的关于CachingCallHandler的Bug

微软EnterLib的Policy Injection Application Block（PIAB）是一个比较好用的轻量级的AOP框架，你可以通过创建自定义的...

• ### 还在用SimpleDateFormat？Java8都发布N年了，转LocalDateTime吧

Java8发布，已有数年之久，但是发现很多人都还是坚持着用SimpleDateFormat和Date进行时间操作。SimpleDateFormat这个类不是线程...

• ### Google 开源的依赖注入库，比 Spring 更小更快！

Guice是Google开源的一个依赖注入类库，相比于Spring IoC来说更小更快。Elasticsearch大量使用了Guice，本文简单的介绍下Guic...

• ### 【一起学系列】之迭代器&组合：虽然有点用不上啦

【产品】：嘿，有一个好消息，咱们旗下的餐厅把月巴克的咖啡店吞并了！太棒了！年终奖稳了！

• ### .NET IoC模式依赖反转(DIP)、控制反转(Ioc)、依赖注入(DI)

依赖倒置(Dependency Inversion Principle,缩写DIP)是面向对象六大基本原则之一。他是指一种特定的的解耦形式,使得高层次的模块不依...

• ### Caffe 实践 - 基于 ResNet101 的 Multi-label 多标签标注的训练与部署

以前曾尝试过修改 Caffe ImageDataLayer 源码的方式来读取多个 labels - ImageMultilabelDataLayer [Caff...

• ### 【源码】基于FPGA的PPPoE协议获取账号密码的攻击实现

对于PPPOE认证上网的过程如下图所示，分为发现阶段和会话阶段，发现阶段分为PADI,PADO,PADR,PADS。