当前位置:首页 > 高性能开发 > 数据结构与算法

数据结构与算法——循环行列

优良自学吧提供数据结构与算法——循环行列,数据结构与算法——循环队列  今天总结循环队列。 什么是队列?    队列跟栈差不多,也是一种操作受限的线性表,只允许在线性表的一端进行插入操作,在另一端进行删除操作。插入的一端称为队尾,删除的一端称为队头,插入操作称为入队,而删除

数据结构与算法——循环队列

  今天总结循环队列。

什么是队列?

   队列跟栈差不多,也是一种操作受限的线性表,只允许在线性表的一端进行插入操作,在另一端进行删除操作。插入的一端称为队尾,删除的一端称为队头,插入操作称为入队,而删除操作称作出出队,不含任何数据元素的队称为空队。队列也有两种实现方式,一种就是顺序存储,用数组实现,另一种是采用链表形式。今天总结顺序存储的循环队列。

什么是循环队列?

   循环队列就是,当队尾指针移动到数组末尾时,下次再有元素入队时,可以将队尾指针重新移到数组前面没有元素的位置。

为什么要使用循环队列?

   循环队列解决了,数组空间利用率的问题。设想,如果每将一个队列出队,则将后面的元素都向前移动,那么这个时候的时间复杂度为O(n),但是如果出队时,我们只将队头指针移向下一位,这样时间复杂度就为O(1),只是当队头指不断后移时,出队元素占用的空间就不能用了,这样队列的可用空间越来越少,当队尾指针到达数组末尾时,再插入元素就不行了,而此时出队的空间其实是可以放入元素的,因此我们就采用循环方式,让队尾指针可以移向前面出队元素的位置,并将元素插入。

数据结构与算法——循环行列

  队列中存在两个指针,一个时队头指针,一个时队尾指针,当队列为空时,则队头与队尾指针相等,均指向数组中的0下标。在队列中,队头所指的元素是不存在队列中,也就是说队头后面的那个元素才是队列的头元素。当队头与队尾指向同一处时(除过数组下标0这个位置),则队已满。

   入队:当队列不满时,则将队尾指针向后移一位,将元素插入到这个位置。

   出队:当队列不满时,将队头指针指向下一位。

   获取队长度:有两种方法。

  • 用rear-front即可得出,但因为是循环队列,所有,有可能rear位置在front前面。当rear在前面时,则QueueSize-(QueueSize-rear-(QueueSize-front))= rear-front+QueueSize
    将两种情况合并可以这样写 (rear-front+QueueSize)%QueueSize
  • 初始化一计数器count,从队头指针开始移动,当rear!=front 就一直循环,计数器不断增1,直到rear==front
具体实现:

 

<span style="font-family:Courier New;font-size:14px;">#include <iostream>

using namespace std;
const int QueueSize = 10;
template <class T>
class CircleQueue {
public:
    CircleQueue() {
        front = rear = 0; //空队列
    }

    void EnQueue(T x);  //入队操作
    T DeQueue();        //出队操作
    T GetFront();       //查找对头元素
    bool IsEmpty() {    //判空队列
        return rear==front?true:false;
    }
    int GetLength();     //队列长度
    void PrintQueue();   //遍历队列
private:
    T data[QueueSize];
    int front;  //队头指针
    int rear;  //队尾指针
};
template <class T>
void CircleQueue<T>::EnQueue(T x) {
    if((rear+1)%QueueSize==front)
        throw "队列为空";
    rear = (rear+1)%QueueSize;  //队尾指针后移
    data[rear] = x;
}
template <class T>
T CircleQueue<T>::DeQueue() {
    if(rear==front)
        throw "队列为空";
    front = (front+1)%QueueSize;
    return data[front];
}

template <class T>
int CircleQueue<T>::GetLength() {
    int count = 0;
    int p = front;
    while(rear!=front) {
        count++;
        front = (front+1)%QueueSize;
    }
    front = p;
    return count;
    //第二种获取队列长度的方法 这里要分两种请框 rear>front
    //和rear<front 合并后就为下面这个 可以仔细推一下
    // return (rear-front+QueeuSize)%QueueSize;
}

template <class T>
T CircleQueue<T>::GetFront() {
    if(front==rear)
        throw "队列为空";
    return data[(front+1)%QueueSize];
}
template <class T>
void CircleQueue<T>::PrintQueue() {
    int p = front;  //保留头指针
    while(front!=rear) {
        cout<<data[(front+1)%QueueSize]<<" ";
        front = (front+1)%QueueSize;  //移动头指针
    }
    front = p;  //队头指针归位
    cout<<endl;
}
int main()
{
    CircleQueue<int> circleQueue;
    for(int i=0;i<9;i++) {
        circleQueue.EnQueue(i);
    }
    cout<<"队列长度"<<endl;
    cout<<circleQueue.GetLength()<<endl;;
    cout<<"遍历队列"<<endl;
    circleQueue.PrintQueue();
    //出队
    circleQueue.DeQueue();
    circleQueue.DeQueue();
    circleQueue.EnQueue(7);
    circleQueue.EnQueue(11);
    cout<<"遍历队列"<<endl;
    circleQueue.PrintQueue();
    cout<<"获取队头元素"<<endl;
    cout<<circleQueue.GetFront()<<endl;

    return 0;
}</span>


 


(本文来自互联网,不代表搜站(http://www.ylzx8.cn/)的观点和立场)
本站所有内容来自互联网,若本站收录的信息无意侵犯了贵司版权,请给我们来信(ylzx8cn@163.com),我们会及时处理和回复,谢谢

最近更新