C#实现队列
2024-09-12 21:01:02
队列(Queue)是插入操作限定在表的尾部而其他操作限定在表的头部进行的线性表。把进行插入操作的表尾称为队尾(Rear).把进行其他操作的头部称为队头(Front).
队列的操作使按照先进先出后进后出的原则进行的。
用一片连续的存储空间来存储队列中的数据元素,称为顺序队列(Sequence Queue)。类似于顺序表,用一维数组来存放队列中的数据元素。
解决顺序队列的假溢出的方法是将顺序队列看成是首位相接的循环结构,叫循环顺序队列(Circular sequence Queue)。
队列的另外一种存储方式是链式存储,称为链队列(Linked Queue)。通常用单链表表示。
Queue using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading; namespace DataStructure
{
/// <summary>
/// 队列接口
/// </summary>
interface IQueue<T>
{
void EnQueue(T elem); //入队列操作
T DeQueue(); //出队列操作
T GetFront(); //取对头元素
int GetLength(); //求队列的长度
bool IsEmpty(); //判断队列是否为空
void Clear(); //清空队列
bool IsFull(); //判断队列是否为满
} /// <summary>
/// 银行队列接口
/// </summary>
interface IBankQueue : IQueue<int>
{
int GetCallnumber(); //获取服务号码
} /// <summary>
/// 循环顺序队列
/// </summary>
/// <typeparam name="T"></typeparam>
class CSeqQueue<T> : IQueue<T>
{
private int maxsize; //循环顺序队列的容量
private T[] data; //数组,用于存储循环顺序队列中的数据元素
private int front; //指示最近一个已经离开队列的元素所占有的位置 循环顺序队列的对头
private int rear; //指示最近一个进入队列的元素的位置 循环顺序队列的队尾 public T this[int index]
{
get { return data[index]; }
set { data[index] = value; }
} //容量属性
public int Maxsize
{
get { return maxsize; }
set { maxsize = value; }
} //对头指示器属性
public int Front
{
get { return front; }
set { front = value; }
} //队尾指示器属性
public int Rear
{
get { return rear; }
set { rear = value; }
} public CSeqQueue()
{ } public CSeqQueue(int size)
{
data = new T[size];
maxsize = size;
front = rear = -;
} //判断循环顺序队列是否为满
public bool IsFull()
{
if ((front == - && rear == maxsize - ) || (rear + ) % maxsize == front)
return true;
else
return false;
} //清空循环顺序列表
public void Clear()
{
front = rear = -;
} //判断循环顺序队列是否为空
public bool IsEmpty()
{
if (front == rear)
return true;
else
return false;
} //入队操作
public void EnQueue(T elem)
{
if (IsFull())
{
Console.WriteLine("Queue is Full !");
return;
}
rear = (rear + ) % maxsize;
data[rear] = elem;
} //出队操作
public T DeQueue()
{
if (IsEmpty())
{
Console.WriteLine("Queue is Empty !");
return default(T);
}
front = (front + ) % maxsize;
return data[front];
} //获取对头数据元素
public T GetFront()
{
if (IsEmpty())
{
Console.WriteLine("Queue is Empty !");
return default(T);
}
return data[(front + ) % maxsize];//front从-1开始
} //求循环顺序队列的长度
public int GetLength()
{
return (rear - front + maxsize) % maxsize;
}
} /// <summary>
/// 链队列结点类
/// </summary>
/// <typeparam name="T"></typeparam>
class QueueNode<T>
{
private T data; //数据域
private QueueNode<T> next; //引用域 public QueueNode(T val, QueueNode<T> p)
{
data = val;
next = p;
} public QueueNode(QueueNode<T> p)
{
next = p;
} public QueueNode(T val)
{
data = val;
next = null;
} public QueueNode()
{
data = default(T);
next = null;
} //数据域属性
public T Data
{
get { return data; }
set { data = value; }
} //引用域属性
public QueueNode<T> Next
{
get { return next; }
set { next = value; }
}
} /// <summary>
/// 链队列类
/// </summary>
/// <typeparam name="T"></typeparam>
class LinkQueue<T> : IQueue<T>
{
private QueueNode<T> front; //队列头指示器
private QueueNode<T> rear; //队列尾指示器
private int size; //队列结点个数 //队列属性
public QueueNode<T> Front
{
get { return front; }
set { front = value; }
} public QueueNode<T> Rear
{
get { return rear; }
set { rear = value; }
} public int Size
{
get { return size; }
set { size = value; }
} //初始化链队列
public LinkQueue()
{
front = rear = null;
size = ;
} public int GetLength()
{
return size;
} public void Clear()
{
front = rear = null;
size = ;
} public bool IsEmpty()
{
if ((front == rear) && (size == ))
return true;
else
return false; } //链队列没有容量限制 返回false
public bool IsFull()
{
return false;
} //入队操作
public void EnQueue(T item)
{
QueueNode<T> q = new QueueNode<T>(item);
if (IsEmpty())
{
front = q;
rear = q;
}
else
{
rear.Next = q;
rear = q;
}
++size;
} //出对操作
public T DeQueue()
{
if (IsEmpty())
{
Console.WriteLine("Queue is Empty !");
return default(T);
}
QueueNode<T> p = front;
front = front.Next; if (front == null)
{
rear = null;
}
--size;
return p.Data;
} //获取链队列头结点的值
public T GetFront()
{
if (IsEmpty())
{
Console.WriteLine("Queue is Empty !");
return default(T);
}
return front.Data;
} } /// <summary>
/// 银行叫号链队列类
/// </summary>
class LinkBankQueue : LinkQueue<int>, IBankQueue
{
private int callnumber; public int Callnumber
{
get { return callnumber; }
set { callnumber = value; }
} //获取服务号码
public int GetCallnumber()
{
if ((IsEmpty()) && callnumber == )
{
callnumber = ;
}
else
callnumber++;
return callnumber;
}
} /// <summary>
/// 银行叫号顺序队列类
/// </summary>
class CSeqBankQueue : CSeqQueue<int>, IBankQueue
{
private int callnumber; //记录系统自动产生的新来顾客的服务号码 public int Callnumber
{
get { return callnumber; }
set { callnumber = value; }
} public CSeqBankQueue()
{ } public CSeqBankQueue(int size)
: base(size)
{ } //获得服务号码
public int GetCallnumber()
{
if ((IsEmpty()) && callnumber == )
{
callnumber = ;
}
else
{
callnumber++;
}
return callnumber;
}
} /// <summary>
/// 服务窗口类
/// </summary>
class ServiceWindow
{
IBankQueue bankQ; //服务队列属性
public IBankQueue BankQ
{
get { return bankQ; }
set { bankQ = value; }
} public void Service()
{
while (true)
{
Thread.Sleep();
if (!bankQ.IsEmpty())
{
Console.WriteLine();
lock (bankQ)
{
Console.WriteLine("请{0}号到{1}号窗口!", bankQ.DeQueue(), Thread.CurrentThread.Name);
}
}
}
}
} class Queue
{ static void Main()
{
IBankQueue bankQueue = null;
Console.WriteLine("请选择存储结构的类型:1.顺序队列 2.链队列:");
char selectFlag = Convert.ToChar(Console.ReadLine());
switch (selectFlag)
{
/*初始化顺序队列*/
case '':
int count; //接受循环顺序队列的容量
Console.WriteLine("请输入队列可容纳的人数:");
count = Convert.ToInt32(Console.ReadLine());
bankQueue = new CSeqBankQueue(count);
break;
/*初始化链队列*/
case '':
bankQueue = new LinkBankQueue();
break; }
int windowcount = ; //设置银行柜台的服务窗口数 ServiceWindow[] sw = new ServiceWindow[windowcount];
Thread[] swt = new Thread[windowcount];
for (int i = ; i < windowcount; i++)
{
sw[i] = new ServiceWindow();
sw[i].BankQ = bankQueue;
swt[i] = new Thread(new ThreadStart(sw[i].Service));
swt[i].Name = "" + (i + );
swt[i].Start();
}
while (true)
{
Console.WriteLine("请点击触摸屏获取号码:");
Console.ReadLine(); int callnumber;
if (!bankQueue.IsFull())
{
callnumber = bankQueue.GetCallnumber();
Console.WriteLine("您的号码是:{0},您前面有{1}位,请等待!", callnumber, bankQueue.GetLength());
bankQueue.EnQueue(callnumber);
}
else
Console.WriteLine("现在业务繁忙,请稍后再来!");
Console.WriteLine();
}
}
}
}
最新文章
- 智力火柴游戏Android源码项目
- 使用air16sdk打包ipa报错
- Python入门笔记(5):对象
- hdu 5802 Windows 10 贪贪贪
- Android init.rc文件格式解析
- [Jsp]防止页面表单重复提交的解决方法
- 快速扫描文本文件,统计行数,并返回每一行的索引位置(Delphi、C#)
- Nexus搭建Maven服务器
- Windows系统下的TCP参数优化
- unity3d打开对话框
- oracle表空间增长异常或表空间占用过高问题分析
- 正则表达式入门+实战(c#实现)
- iOS开发之七:常用控件--UISlider、UISegmentedControl、UIPageControl的使用
- 《React设计模式与最佳实践》笔记
- Vue自定义class覆盖第三方组件原有样式
- RESTful Loads
- cocos2d-x 错误异常抛出捕获和崩溃拦截
- RocketMQ-quickstart(批量消费)
- Storm 安装部署
- 为Hadoop集群选择合适的硬件配置