sponsored links

C++实现队列(循环队列)

一、队列的操作:

、1、入队(从尾入队)

  • 将值存入rear所代表的位置
  • rear = (rear + 1)% 数组的长度

2、 出队(头部出队)

  • front = (front + 1)% 数组的长度

3、 队列是否为空

  • front 和 rear的值相等,则该队列就一定为空

4、队列是否已满

在循环队列中“队满”和“队空”的条件有可能是相同的,都是front == rear 这种情况下,无法区别是“队满”还是“队空”。针对这个问题有3种可能的处理方式:

(1)另设一个标志以区别是“队满”还是”队空“。

(2)设一个计数器,此时甚至还可以省去一个指针

(3)少一个元素空间,即约定队头指针在队尾指针的下一个位置时就作为”队满“的标志,即”队满“条件为:(pQueue->rear + 1)%MAX_SIZE == pQueue->front。

二、队列的一些问题及解决办法

C++实现队列(循环队列)

从上图可以看出,随着入队、出队的进行,会使整个队列整体向后移动,就会出现上图种的现象:队尾指针已经移到了最后,即队尾出现溢出,无法再进行入队操作,然而实际上,此时队列中还是有空闲空间,这种现象称为”假溢出“,解决假溢出的三种办法:

方法一:每次删除队头元素后,把整个队列向前移动一个位置,这样可保证队头元素在存储空间的最前面。但每次删除元素时,都要把表中所有元素向前移动,效率太低。

方法二:当队尾指针出现溢出时,判断队头指针位置,如果前部有空闲空间,则把当前队列整体前移到最前方。这种方法移动元素的次数大为减少。

方法三:将队列看成头尾相接的循环结构,当队尾指针到队尾后,再从队头开始向后指,这样就不需要移动队列元素了,显然,第三种方法最经济、应用最多,这种顺序队列被称为“循环队列”或“环形队列”。

采用了这种头尾相接的循环队列后,入队的队尾指针加1操作及出队的队头指针加1操作必须做相应的修改,以确保下标范围为0~Max_Size-1。对指针进行取模运算,就能使指针到达最大下标位置后回到0,符合“循环”队列的特点。

因此入队时队尾指针加1操作改为: pQueue->tail = (pQueue->tail+1) % MAX_SIZE;

入队时队尾指针加1操作改为: pQueue->head = (pQueue->head+1) % MAX_SIZE;

#ifndef QUEUE_H
#define  QUEUE_H

typedef class queue
{
public:
    queue(int len = 10);
    queue(const queue& src);
    queue operator=(const queue& src);
    ~queue();

    void push(int val);
    void pop();
    int getHead();

    bool isEmpty();
    bool isFull();
    void resize();

    void show();
private:
    int *_arr;
    int _head;
    int _tail;
    int _len;
}Queue,*Pqueue;

#endif
#include"queue.h"
#include<iostream>
using namespace std;

queue::queue(int len)
{
    if (len < 10)
    {
        len = 10;
    }

    _arr = new int[len];
    _head = 0;
    _tail = 0;
    _len = len;
}

queue::queue(const queue& src)
{
    _arr = new int[src._len];
    _len = src._len;
    _head = src._head;
    _tail = src._tail;

    for (int i = _head; i != _tail; i=(i + 1) % _len)
    {
        _arr[i] = src._arr[i];
    }
}

queue queue::operator=(const queue& src)
{
    if (this == &src)
    {
        return *this;
    }

    if (_arr != NULL)
        delete []_arr;

    _arr = new int[src._len];
    _len = src._len;
    _head = src._head;
    _tail = src._tail;

    for (int i = _head; i != _tail; i=(i + 1) % _len)
    {
        _arr[i] = src._arr[i];
    }

    return *this;
}

queue::~queue()
{
    if (_arr != NULL)
        delete[]_arr;

    _arr = NULL;
    _len = 0;
    _tail = 0;
    _head = 0;
}

void queue::push(int val)
{
    if (isFull())
    {
        resize();
    }

    _arr[_tail] = val;
    _tail = (_tail + 1) % _len;
}

void queue::pop()
{
    if (isEmpty())
    {
        return;
    }

    _head = (_head + 1) % _len;
}

int queue::getHead()
{
    if (isEmpty())
    {
        return -1;
    }

    return _arr[_head];
}

bool queue::isEmpty()
{
    return _tail == _head;
}

bool queue::isFull()
{
    return (_tail + 1) % _len == _head;
}

void queue::resize()
{
    int len = _len + (_len >> 1);
    int *tmp = new int[len];

    for (int i = _head, j = 0; i != _tail; i = (i + 1) % _len,j++)
    {
        tmp[j] = _arr[i];
    }

    if (_arr !=NULL)
        delete[]_arr;
    _arr = NULL;

    _arr = tmp;

    _head = 0;
    _tail = _len - 1;
    _len = len;
}

void queue::show()
{
    for (int i = 0; i < _len; i++)
    {
        cout << _arr[i] << "  ";
    }
    cout << endl;
    cout << "head:" << _head << endl;
    cout << "tail:" << _tail << endl;
    cout << "len:" << _len << endl;
}
#include"queue.h"
#include<iostream>
using namespace std;

int main()
{
    Queue que;
    for (int i = 0; i < 9; i++)
    {
        que.push(i);
    }
    que.show();

    for (int i = 0; i < 3; i++)
    {
        cout << que.getHead() << endl;
        que.pop();
    }

    que.show();
    for (int i = 0; i < 3; i++)
    {
        que.push(i + 10);
    }
    que.show();
    for (int i = 0; i < 3; i++)
    {
        que.push(i + 20);
    }
    que.show();

    Queue que1 = que;
    que1.show();

    Queue que2;
    que2 = que1;
    que2.show();

    return 0;
}
Tags: