循环队列与队列的链式结构

发表评论
22,281 views

A+

所属分类：Fly数据结构与算法原创文章

队列就是一种受限的线性表

它规定先进先出

也就是说只能在表尾插入数据

在表头提出数据

下面实现队列的顺序存储结构

这里只实现最有价值的循环队列

也就是

队尾下一位指针可以由数组的后面从新在指向数组的前面

只要数组的位置是空的

而队头指针也一样，也是可以不停向后，然后从头开始

//队列的顺序存储结构-循环队列
class QueueCycleList<T>
{
    private T[] _data;
    private int _front;
    private int _rear;
    private int _maxLength = 24;

    public QueueCycleList() {
        //留一个空位，用于判断队满的情况
        this._data = new T[this._maxLength+1];
        _front = _rear = 0;
    }

    public QueueCycleList(int length) {
        if (length > 0) {
            this._maxLength = length;
        }

        this._data = new T[this._maxLength+1];
        this._front = this._rear = 0;
    }

//队列的顺序存储结构-循环队列

class QueueCycleList<T>

{

private T[] _data;

private int _front;

private int _rear;

private int _maxLength = 24;

public QueueCycleList() {

//留一个空位，用于判断队满的情况

this._data = new T[this._maxLength+1];

_front = _rear = 0;

}

public QueueCycleList(int length) {

if (length > 0) {

this._maxLength = length;

}

this._data = new T[this._maxLength+1];

this._front = this._rear = 0;

}

_data数组用于保存数据

_front指向队头

_rear指向队尾的下一个空位

_maxLength可以保存数据的最大长度

两个构造函数初始化化队列为空（_front == _rear）

初始化数组的大小为保存数据长度+1

是因为要留一个空位来去判断队列是否已满

如果不留，那么队满也是_front == _rear

这样就冲突了

当然可以设置一个标志位

public bool isEmpty() {
    if (this._rear == null) {
        return true;
    }

    return false;
}

public bool isFull() {
    int next = (this._rear + 1) % (this._maxLength + 1);
    if (next == this._front) {
        return true;
    }

    return false;
}

public bool isEmpty() {

if (this._rear == null) {

return true;

}

return false;

}

public bool isFull() {

int next = (this._rear + 1) % (this._maxLength + 1);

if (next == this._front) {

return true;

}

return false;

}

判断是否为空和是否为满

前面已经说过

如果队头和队尾指针同时指向同一个

那么就是为空

那么重点说说为满

前面也说过，留了一位用于判断队满情况

那么可以是

也可以是

也就是说rear指针可能比front大

也可能比它小

但它们在数组范围内只相差一位

共同的方法就是将rear+1后求余于数组的长度

那就是循环队列的rear的下一位了

这个在后面指针移动时都要用到

//入队
public bool EnQueue(T element) {
    if (this.isFull()) {
        Console.WriteLine("队列已满！");
        return false;
    }

    this._data[this._rear] = element;
    //指标向下移动
    this._rear = (this._rear + 1) % (this._maxLength + 1);
    return true;
}

//入队

public bool EnQueue(T element) {

if (this.isFull()) {

Console.WriteLine("队列已满！");

return false;

}

this._data[this._rear] = element;

//指标向下移动

this._rear = (this._rear + 1) % (this._maxLength + 1);

return true;

}

入队的话

①先判断一下队列有没有满

②没有满的话就插入数据

因为rear指针指向的是队尾的下一个

也就是空位置，所以直接插入就行了

③将尾指针后移一位，前面已经说过后移一位的方法

//出队
public bool DeQueue(ref T element) {
    if (this.isEmpty()) {
        Console.WriteLine("队列为空！");
        return false;
    }

    element = this._data[this._front];
    //指标向前移动
    this._front = (this._front + 1) % (this._maxLength + 1);
    return true;
}

//出队

public bool DeQueue(ref T element) {

if (this.isEmpty()) {

Console.WriteLine("队列为空！");

return false;

}

element = this._data[this._front];

//指标向前移动

this._front = (this._front + 1) % (this._maxLength + 1);

return true;

}

出队的话

①先判断一下队列是否为空

②不为空的话输出队头数据，front指向的数据

③队头指针向后移动一位

//清空
public void Clear() {
    while (this._front != this._rear) {
        this._data[this._front] = default(T);
        this._front = (this._front + 1) % (this._maxLength + 1);
    }

    this._rear = this._front = 0;
}

//清空

public void Clear() {

while (this._front != this._rear) {

this._data[this._front] = default(T);

this._front = (this._front + 1) % (this._maxLength + 1);

}

this._rear = this._front = 0;

}

在队列不为空(front == rear)之前

循环清楚数据，将队列清空

并赋值头尾从0开始

//获取循环队列长度
public int GetLength() {
    int maxLength = this._maxLength + 1;
    return (this._rear - this._front + maxLength) % maxLength;
}

//获取循环队列长度

public int GetLength() {

int maxLength = this._maxLength + 1;

return (this._rear - this._front + maxLength) % maxLength;

}

这个重点说一下

分两种情况

①就是队尾rear指针大于队头指针front

length = rear - front

②队尾rear指针小于队头指针front

这种情况就分两段

length1 = 数组长度 - front

length2 = rear

length = length1 + length2

= rear - front + 数组长度

那么综合两个情况

可以总结出

队列的长度为：

（rear - front + 数组长度）% 数组长度

测试

static void TestQueueCycleList() {
    QueueCycleList<int> q = new QueueCycleList<int>(4);
    q.EnQueue(2);
    q.EnQueue(22);
    q.EnQueue(30);
    q.EnQueue(55);
    q.EnQueue(66);
    Console.WriteLine("队列是否为空："+q.isEmpty());
    Console.WriteLine("队列是否已满：" + q.isFull());
    Console.WriteLine("队列长度：" + q.GetLength());
    int e = 0;
    Console.Write("依次出队为：");
    while (!q.isEmpty()) {
                
        q.DeQueue(ref e);
        Console.Write(e+ " ");
    }
    Console.WriteLine();
    Console.WriteLine();


    q.EnQueue(30);
    q.DeQueue(ref e);
    q.DeQueue(ref e);
    Console.WriteLine("队列是否为空：" + q.isEmpty());
    Console.WriteLine("队列是否已满：" + q.isFull());
    Console.WriteLine("队列长度：" + q.GetLength());
    Console.WriteLine();


    q.EnQueue(66);
    q.EnQueue(22);
    Console.WriteLine("队列是否为空：" + q.isEmpty());
    Console.WriteLine("队列是否已满：" + q.isFull());
    Console.WriteLine("队列长度：" + q.GetLength());
    Console.Write("依次出队为：");
    while (!q.isEmpty())
    {

        q.DeQueue(ref e);
        Console.Write(e + " ");
    }
    Console.WriteLine();


    q.EnQueue(20);
    Console.WriteLine("队列长度：" + q.GetLength());
    q.Clear();
    Console.WriteLine("队列长度：" + q.GetLength());

}

static void TestQueueCycleList() {

QueueCycleList<int> q = new QueueCycleList<int>(4);

q.EnQueue(2);

q.EnQueue(22);

q.EnQueue(30);

q.EnQueue(55);

q.EnQueue(66);

Console.WriteLine("队列是否为空："+q.isEmpty());

Console.WriteLine("队列是否已满：" + q.isFull());

Console.WriteLine("队列长度：" + q.GetLength());

int e = 0;

Console.Write("依次出队为：");

while (!q.isEmpty()) {

q.DeQueue(ref e);

Console.Write(e+ " ");

}

Console.WriteLine();

q.EnQueue(30);

q.DeQueue(ref e);

Console.WriteLine("队列是否为空：" + q.isEmpty());

Console.WriteLine("队列是否已满：" + q.isFull());

Console.WriteLine("队列长度：" + q.GetLength());

Console.WriteLine();

q.EnQueue(66);

q.EnQueue(22);

Console.WriteLine("队列是否为空：" + q.isEmpty());

Console.WriteLine("队列是否已满：" + q.isFull());

Console.WriteLine("队列长度：" + q.GetLength());

Console.Write("依次出队为：");

while (!q.isEmpty())

{

q.DeQueue(ref e);

Console.Write(e + " ");

}

Console.WriteLine();

q.EnQueue(20);

Console.WriteLine("队列长度：" + q.GetLength());

q.Clear();

Console.WriteLine("队列长度：" + q.GetLength());

}

结果

队列的链式存储结构

class QueueLink<T>
{
    class Node {
        public T data;
        public Node next;
    }

    private Node _front;
    private Node _rear;
    private int _currentLength = 0;

    public QueueLink() {
        //新建一个头结点
        Node head = new Node();
        head.next = null;
        this._front = this._rear = head;
    }

    //入队
    public bool EnQueue(T element) {
        Node addNode = new Node();
        addNode.data = element;
        addNode.next = this._rear.next;

        this._rear.next = addNode;
        this._rear = addNode;
        this._currentLength++;
        return true;
    }

    //出队
    public bool DeQueue(ref T element) {
        if (this.isEmpty()) {
            Console.WriteLine("队列为空！");
            return false;
        }

        Node getNode = this._front.next;
        element = getNode.data;

        if (this._rear == getNode) {
            //队列中只有一个元素
            this._rear = this._front;
        }
        this._front.next = getNode.next;
        getNode = null;
        this._currentLength--;
        return true;
    }

    //清空
    public void Clear() {
        Node deleteNode = this._front.next;
        while (deleteNode != null) {
            Node go = deleteNode.next;
            deleteNode = null;
            deleteNode = go;
        }

        this._rear = this._front;
        this._currentLength = 0;
    }

    public bool isEmpty() {
        if (this._front == this._rear) {
            return true;
        }

        return false;
    }

    public int GetLength() {
        return this._currentLength;
    }
}

class QueueLink<T>

{

class Node {

public T data;

public Node next;

}

private Node _front;

private Node _rear;

private int _currentLength = 0;

public QueueLink() {

//新建一个头结点

Node head = new Node();

head.next = null;

this._front = this._rear = head;

}

//入队

public bool EnQueue(T element) {

Node addNode = new Node();

addNode.data = element;

addNode.next = this._rear.next;

this._rear.next = addNode;

this._rear = addNode;

this._currentLength++;

return true;

}

//出队

public bool DeQueue(ref T element) {

if (this.isEmpty()) {

Console.WriteLine("队列为空！");

return false;

}

Node getNode = this._front.next;

element = getNode.data;

if (this._rear == getNode) {

//队列中只有一个元素

this._rear = this._front;

}

this._front.next = getNode.next;

getNode = null;

this._currentLength--;

return true;

}

//清空

public void Clear() {

Node deleteNode = this._front.next;

while (deleteNode != null) {

Node go = deleteNode.next;

deleteNode = null;

deleteNode = go;

}

this._rear = this._front;

this._currentLength = 0;

}

public bool isEmpty() {

if (this._front == this._rear) {

return true;

}

return false;

}

public int GetLength() {

return this._currentLength;

}

与普通的链表差不多

只是只能在队头删除并取出元素

在队尾插入元素

这里就不详细说了

方法的实现说明可以参考前面线性表的链式结构

测试

static void TestQueueLink() {
    QueueLink<int> q = new QueueLink<int>();
    q.EnQueue(6);
    q.EnQueue(5);
    q.EnQueue(80);
    Console.WriteLine("队列是否为空：" + q.isEmpty());
    Console.WriteLine("队列长度：" + q.GetLength());
    int e = 0;
    Console.Write("依次出队为：");
    while (!q.isEmpty())
    {

        q.DeQueue(ref e);
        Console.Write(e + " ");
    }
    Console.WriteLine();
    Console.WriteLine();

    Console.WriteLine("队列是否为空：" + q.isEmpty());
    Console.WriteLine("队列长度：" + q.GetLength());
    Console.WriteLine();

    q.EnQueue(22);
    q.EnQueue(33);
    Console.Write("依次出队为：");
    while (!q.isEmpty())
    {

        q.DeQueue(ref e);
        Console.Write(e + " ");
    }
}

static void TestQueueLink() {

QueueLink<int> q = new QueueLink<int>();

q.EnQueue(6);

q.EnQueue(5);

q.EnQueue(80);

Console.WriteLine("队列是否为空：" + q.isEmpty());

Console.WriteLine("队列长度：" + q.GetLength());

int e = 0;

Console.Write("依次出队为：");

while (!q.isEmpty())

{

q.DeQueue(ref e);

Console.Write(e + " ");

}

Console.WriteLine();

Console.WriteLine("队列是否为空：" + q.isEmpty());

Console.WriteLine("队列长度：" + q.GetLength());

Console.WriteLine();

q.EnQueue(22);

q.EnQueue(33);

Console.Write("依次出队为：");

while (!q.isEmpty())

{

q.DeQueue(ref e);

Console.Write(e + " ");

}

结构

发表评论取消回复

登录 注册 找回密码

登录注册找回密码