数据结构——队列

概念

具有一定操作约束的线性表。

只能在一端插入，而在另一端删除。

数据插入：入队

数据删除：出队

（先来先出）

循环队列：

顺序存储（数组）

#define MaxSize <最大个数>
struct QNode{
	ElementType Data[MaxSize];    
    int rear;
    int front;
};

入队列

void AddQ(QNode* PtrQ,ElementType item)
{
    //求余是判断是否满了，满了从头开始（循环队列）
    if((PtrQ->rear+1)%MaxSize == PtrQ->front){
        cout << "队列满";
        return;
    }
    PtrQ->rear = (PtrQ->rear+1)%MaxSize;
    PtrQ->Data[PtrQ->rear] = item;
}

出队列

ElementType DeleteQ(QNode* PtrQ)
{
    if(PtrQ->rear==PtrQ->front){
        cout << "队列空";
        return ERROR;
    }else {
        PtrQ->front=(PtrQ->front+1)%MaxSiz;
        return PtrQ->Data[PtrQ->front];
    }
}

链表实现

链表头做删除操作（front）

链表尾做插入操作（rear）

struct Node{
    ElementType Data;
    struct Node *Next;
};
struct QNode{
    struct Node *rear;
    struct Node *front;
};
QNode *PtrQ;

入队

void AddQ(ElementType X,QNode *PtrQ){
    NOde *Cell;
    Cell=(QNode*)new QNode;
    Cell->Data=X;
    Cell->Next=NULL;
    PtrQ->rear=Cell;
}

出队

ElementType Delete(QNode* PtrQ){
    Node* Cell;
    ElementType FrontElem;
    if(PtrQ->front==NULL){
        cout << "链表为空";
        return ERROR;
    }
    Cell=PtrQ->front;
    FrontElem=PtrQ->front->Data;
    if(PtrQ->front==PtrQ->rear){
        //说明只有一个元素删了后链表为空
        PtrQ->front=PtrQ->rear=NULL;
    }else {
        PtrQ->front=PtrQ->front->Next;
    }
    delete Cell;
    return FrontElem;
}