队列基本操作（链式结构）

朱雀 2022-08-02 01:53 178阅读 0赞

**基本概念：**  
队列：是只允许在一端进行插入操作，而在另一端进行删除操作的线性表（或单链表，无头结点）。  
即：先进先出  
队尾：允许插入的一端；队头：允许删除的一端

**队列示意图如下：**  
注意next指针的指向与链栈不同  
![这里写图片描述][20150705210813402]

**代码如下：**

#include <iostream>
    
    using namespace std;
    
    typedef struct node{
        int data;
        struct node *next;
    }Node;
    
    typedef struct queue_type{
        Node *front;       /*队头*/
        Node *rear;        /*队尾*/
    }Queue_t;
    
    /**创建空队列*/
    Queue_t * Create_null_queue()
    {
        Queue_t *p;       /**Queue_t：只有在创建的时候才有作用。*/
        p = new Queue_t;
        p->front = NULL;
        p->rear = NULL;
    
        return p;
    }
    
    /**队列的入队操作，即在队尾插入*/
    Queue_t * Insert_queue(Queue_t *p,int elem)
    {
        if(NULL == p)              /**如果p本身为空*/
            return NULL;
    
        Node *temp;
        temp = new Node;
        temp->data = elem;
        temp->next = NULL;
    
        if(NULL == p->rear)        /**如果队列为空*/
        {
            p->front = temp;       /**队头、队尾都指向这个节点*/
            p->rear = temp;
        }
        else{
            p->rear->next = temp;  /**将队尾指向的节点的 next 指向temp，即将temp接在后面*/
            p->rear = temp;        /**队尾向后移动一位*/
        }
    
        return p;
    }
    
    /**出队操作，从队头删除一个节点*/
    Queue_t * Delete_queue(Queue_t *p)
    {
        Node *temp;                   /**temp：是一个指向Node的指针，p->front：也是一个指向Node的指针*/
        temp = p->front;              /**这里不能写成：Queue *temp; temp = p->front; 因为这样，temp就不是一个指向Node的指针了，两者不能相等*/
    
        if(NULL == temp)              /**队列为空，是 p->front = NULL*/
        {
            cout << "The queue is empty" << endl;
            return p;
        }
    
        p->front = p->front->next;
    
        if(NULL == p->front)         /**如果这个元素是最后一个元素，队尾指针也需要置为空*/
            p->rear = NULL;
        delete temp;
    
        return p;
    }
    
    /**队列的输出操作*/
    int Show_queue(Queue_t *p)
    {
        Node *temp;
        temp = p->front;
    
        if(NULL == temp)
        {
            cout << "The Queue is empty" << endl;
            return 0;
        }
    
        while(NULL != temp)
        {
            cout << temp->data << ' ';
            temp = temp->next;
        }
        cout << endl;
    
        return 0;
    }
    
    int main()
    {
        Queue_t *p;
        int i = 5;
        int elem;
    
        p = Create_null_queue();
    
        while(i--)
        {
            cin >> elem;
            Insert_queue(p,elem);
        }
        cout << "空栈插入5个元素后:" << endl;
        Show_queue(p);
    
        Delete_queue(p);
        cout << "删除1个元素后:" << endl;
        Show_queue(p);
    
        Insert_queue(p,6);
        cout << "插入元素6后:" << endl;
        Show_queue(p);
    
        for(i = 5;i--;)
            Delete_queue(p);
        cout << "删除5个元素后:" << endl;
        Show_queue(p);
    
        return 0;
    }

结果如下：  
![这里写图片描述][20150705211009721]

/*点滴积累，我的一小步O(∩\_∩)O~*/

[20150705210813402]: /images/20220731/f01ce2939ba94cb9820273f722d0a52f.png
[20150705211009721]: /images/20220731/4312e280461e426c9172c4207d43ae00.png