数据结构之队列

2018-06-17 20:55:21来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

队列

    1.定义:队列是一种先进先出(FIFO)的线性表。它只允许在表的一端进行插入,而在另一端删除元素。

在队列中,允许插入的一端叫做队尾,允许删除的一端则称为队头。

    假设对列为q=(a1,a2,a3,...,an),那么a1就是队头元素,an则是队尾元素。队列中的元素是按照a1,a2

,...,an的顺序进入的,退出队列也只能按照这个次退出,也就是说,只有在a1,a2,...,an-1都离开队列之后,

an才能退出队列。那么其数据结构为:

#define ElemType int
#define QUEUE_INIT_SIZE 8

typedef struct Queue
{
    ElemType *base;
    int       capacity;
    int       front;
    int       rear;
}Queue;

        2.因此在队列中有以下操作:

void InitQueue(Queue *q);
void EnQueue(Queue *q, ElemType x);
void DeQueue(Queue *q);
ElemType GetTop(Queue *q);
void ShowQueue(Queue *q);
bool IsFull(Queue *q);
bool IsEmpty(Queue *q);

     以上的方法在队列中有以下操作:(1)初始化队列.(2)向队列中插入元素.(3)删除队列中的元素.(4)

得到队头元素.(5)展示队列中的内容.(6)判断队列是否是满状态.(7)判断队列是否是空状态.

   3.将上面声明的方法进行实现为:

bool IsFull(Queue *q)
{
    //return (q->rear-q->front) >= q->capacity;
    //return q->rear >= q->capacity;
    return (q->rear+1)%q->capacity == q->front;
}
bool IsEmpty(Queue *q)
{
    return q->front == q->rear;
}
void InitQueue(Queue *q)
{
    q->base = (ElemType*)malloc(sizeof(ElemType)*QUEUE_INIT_SIZE);
    assert(q->base != NULL);
    q->capacity = QUEUE_INIT_SIZE;
    q->front = q->rear = 0;
}
void EnQueue(Queue *q, ElemType x)
{
    if(!IsFull(q))
    {
        q->base[q->rear] = x;
        q->rear = (q->rear+1) % q->capacity;
    }
}

void ShowQueue(Queue *q)
{
    if(!IsEmpty(q))
    {
        for(int i=q->front; i!=q->rear; i=(i+1)%q->capacity)
        {
            cout<<q->base[i]<<" ==> ";
        }
        cout<<endl;
    }
}

void DeQueue(Queue *q)
{
    if(!IsEmpty(q))
    {
        q->front++;
        q->front = q->front % q->capacity;
    }
}

ElemType GetTop(Queue *q)
{
    assert(!IsEmpty(q));
    return q->base[q->front];
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:BZOJ 1588: [HNOI2002]营业额统计

下一篇:21.C++- &quot;++&quot;操作符重载、隐式转换之explicit关键字、