526互联

ds:队列的基本实现

发布时间 2023-07-09 13:20:03作者: as阿水

 

一.顺序队

1.入队判断队满，出队判断队空;

2.顺序队定义时，要注意front、rear是下标，不是指针。

typedef struct{
    int data[maxsize];
    int rear,front;        // front：队头元素的下标。rear：队尾元素的后一个位置的下标(下一个待插入的位置)，
}sqListQueue;

3,如果判断队满的条件是Q.front = (Q.rear+1)%maxsize，那么就要占用maxsize中一个位置来存放Q.rear指向，为了避免空间浪费就引入了tag、size判断队满

4.---使用tag时，初始化时tag=0，只有入队时将tag改为1，出队时tag改为0。判断队满：Q.rear==Q.front && Q.tag==1;队空：Q.rear == Q.front && Q.tag==0。

5..---使用size时，初始化时size=0，入队时size++，出队时size--。判断队满：Q.size == maxsize；队空：Q.size==0。

 

二.链队

1.出队判断队空；出队还需要判断当前结点是否是最后一个结点，如果是，需要把Q.rear指向Q.front

bool outQueue(LinkQueue &Q,int &e){
    if(isEmpty(Q)){     // 出队：判队空
        return false;
    }
    Node *p = Q.front->next;
    e = p->data;
    if(Q.rear == p){    // 出队：若出队结点为最后一个结点，则需要把队尾指向队头
        Q.rear = Q.front;
    }
    Q.front->next = p->next;
    free(p);
    cout << "deQueue suc, data: " << e << endl;
    return true;
}

2.链队的实现需要注意：要先定义一个单链表，再定义一个队列。

// 链队：从表尾进（rear->next），从表头出(front->next)。带头结点的链队。front->L->a1->a2
typedef struct Node{
    int data;
    struct Node *next;
}Node;      // 链队结点

typedef struct{
    struct Node *front,*rear;
}LinkQueue;     // 队列，结点类型为单链表结点，在单链表结点上又加了front、rear指针

3.如果是带头结点单链表，初始化时要定义一个头结点，让队头指针、队尾指针都指向这个头结点。不带头结点的单链表实现的队列初始化时直接把队头队尾指针指向NULL即可。

void initQ(LinkQueue &Q){
    Q.front = Q.rear = (Node *)malloc(sizeof(Node));
    Q.front->next = NULL;
}　

4.