XIAOSUO 记录个人学习的足迹

一、概述

　　FIFO: First In, First Out（先进先出）
　　受限的线性表，在一端插入，在另一端删除。

二、栈的操作

1.入队列操作EnQueue (T item) ：

　　将值为item的新数据元素添加到队尾，队列发生变化。
2.出队列操作DeQueue ()：

　　将对头元素从队列中取出，队列发生变化。
3.取队头元素GetFront () ：

　　返回队头元素的值，队列不发生变化。
4.求队列的长度GetLength()：

　　返回队列中数据元素的个数。
5.判断队列是否为空IsEmpty()：

　　如果队列为空返回true，否则返回false。
6.清空操作Clear()：

　　使队列为空。

三、队列的顺序表示和实现

　　用一片连续的存储空间来存储队列中的数据元素，这样的队列称为顺序队列。类似于顺序栈，用一维数组来存放顺序队列中的数据元素。队头设置在最近一个己经离开队列的元素所占的位置，用front表示。队尾设置在最近一个进行入队列的元素的位置，用rear表示。根据循环队列的概念我们很容易知道队列为空的判断条件是rear = front；而队列为满时的判断条件同样也是rear = front。为了解决空队列和满队列的判断问题，我们总是留一个空位置不让起插入数据。当队列为满的条件变成rear + 1 == front。

　　顺序队列因多次入队列和出队列操作后出现的有存储空间但不能进行入队列操作的溢出称为假溢出。假溢出是由于队列“队尾入队队头出队”的操作原则造成的。解决假溢出的方法是将顺序队列看成是首尾相接的循环结构，头尾指示器的关系不变，这种队列叫循环顺序队列。队尾指示器的加1操作：rear = (rear + 1) % maxsize。队头指示器的加1操作：front = (front + 1) % maxsize。

　　基本运算在顺序队列上的实现如下：

public class SeqQueue<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 SeqQueue(int size)
	{
		data = new T[size];
		maxsize = size;
		front = rear = -1;
	}
   
	public void EnQueue(T elem)
	{
		if (IsFull())
		{
			throw new Exception("队列已满，不能再插入了。");
		}
		rear = (rear + 1) % maxsize; ;
		data[rear] = elem;
	}
   
	public T DeQueue()
	{
		if (IsEmpty())
		{
			return default(T);
		}
		front = (front + 1) % maxsize;
		return data[front];
	}
   
	public T GetFront()
	{
		if (IsEmpty())
		{
			return default(T);
		}
		return data[(front + 1) % maxsize];
	}
   
	public int GetLength()
	{
		return (rear - front + maxsize) % maxsize;

	}
  
	public void Clear()
	{
		front = rear = -1;
	}
 
	public bool IsEmpty()
	{
		if (front == rear)
		{
			return true;
		}
		else
		{
			return false;
		}
	}

	private bool IsFull()
	{
		if ((front == -1 && rear == maxsize - 1) || (rear + 1) % maxsize == front)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
}

四、队列的链式表示和实现

　　用链式存储结构存储的队列称为链队列。链队列结点的结构与单链表结点的结构一样。链队列大多采用带头结点的链队列，设队头指针为front，再设一个队尾指针指向链队列的末尾。

　　基本运算在链队列上的实现如下：

public class LinkQueue<T>
{
	private Node<T> front;  //队列头指示器 
	private Node<T> rear;   //队列尾指示器 
	private int size;       //队列结点个数 

	public Node<T> Front
	{
		get
		{
			return front;
		}
		set
		{
			front = value;
		}
	}

	public Node<T> Rear
	{
		get
		{
			return rear;
		}
		set
		{
			rear = value;
		}
	}

	public int Size
	{
		get
		{
			return size;
		}
		set
		{
			size = value;
		}
	}

	public LinkQueue()
	{
		front = rear = null;
		size = 0;
	}

	public void EnQueue(T item)
	{
		Node<T> q = new Node<T>(item);
		if (IsEmpty())
		{
			front = q;
			rear = q;
		}
		else
		{
			rear.Next = q;
			rear = q;
		}

		++size;
	}
   
	public T DeQueue()
	{
		if (IsEmpty())
		{
			return default(T);
		}
		Node<T> p = front;
		front = front.Next;
		if (front == null)
		{
			rear = null;
		}
		--size;
		return p.Data;
	}
   
	public T GetFront()
	{
		if (IsEmpty())
		{
			return default(T);
		}
		return front.Data;
	}
  
	public int GetLength()
	{
		return size;
	}
 
	public void Clear()
	{
		front = rear = null;
		size = 0;
	}
  
	public bool IsEmpty()
	{
		if ((front == rear) && (size == 0))
		{
			return true;
		}
		else
		{
			return false;
		}
	}
}