队列

作者: lpworkstudy | 来源:发表于2017-09-26 13:33 被阅读0次

    概念

    是一种只能在表尾进行插入,表头进行删除操作的特殊线性表

    1. 使用顺序存储结构

    #include<stdio.h>
    #include<stdlib.h>
    #include<stdbool.h>
    
    /*队列的基本操作就是入队和出队
    入队:从队列尾部插入
    出队: 从队列头部删除
    FIFO
    */
    #define CAPACITY 100
    typedef int DataType;
    typedef struct SeqQueue
    {
       int front; // 头索引
       int rear;  //尾部索引
       int size;  //当前长度
       unsigned capacity; //最大容量
       DataType * data;
    
    
    } Queue;
    
    // 初始化队列
    
    void Initialize(Queue * q)
    {
       q->capacity = CAPACITY;
       q->front = q->size = 0;
       q->rear = q->capacity - 1;
       q->data = (DataType *)malloc(sizeof(DataType)*CAPACITY);
    
    }
    
    // 判断队列是否为空
    bool IsEmpty(Queue * q)
    {
       if (q->size == 0)
           return true;
       else
           return false;
    }
    
    //判断队列是否为满
    bool IsFull(Queue *q)
    {
       if(q->size == q->capacity)
           return true;
       else
           return false;
    }
    
    //入队操作
    void Enqueue(Queue * q,DataType item)
    {
       if(IsFull(q))
           return;
       q->rear = (q->rear + 1) % q->capacity;
       q->data[q->rear] = item;
       q->size++;
       printf("%d enqueued to queue\n",item);
       printf("size = %d\n",q->size);
    }
    
    //出队操作
    DataType Dequeue(Queue * q)
    {
    
       if (IsEmpty(q))
           return ;
    
       DataType item;
       item = q->data[q->front];
       q->front = (q->front + 1) % q->capacity;
       q->size--;
       printf("%d \n",q->size);
       printf("%d dequeue \n",item);
       return item;
    }
    
    DataType front (Queue * q)
    {
       if (IsEmpty(q))
           return NULL;
       return q->data[q->front];
    }
    DataType rear(Queue * q)
    {
       if (IsEmpty(q))
           return NULL;
       return q->data[q->rear];
    }
    
    int main(void)
    {
       Queue queue;
       Initialize(&queue);
       Enqueue(&queue,10);
       Enqueue(&queue,20);
       Enqueue(&queue,30);
       Enqueue(&queue,40);
    
       Dequeue(&queue);
       Dequeue(&queue);
       printf("Front item is %d\n",front(&queue));
       printf("Rear item is %d\n",rear(&queue));
       return 0;
    }
    

    2. 使用链式存储

    #include<stdio.h>
    #include<stdlib.h>
    #include<stdbool.h>
    
    //定义结点
    typedef int DataType;
    typedef struct node
    {
        DataType data;
        struct node * next;
    }Node;
    
    typedef struct queue
    {
        Node * front;
        Node * rear;
    }Queue;
    
    //初始化队列
    void Initialize(Queue * q)
    {
        q->front = q->rear = NULL;
    }
    //创建一个新结点
    Node * newNode(DataType x)
    {
        Node * temp = (Node*)malloc(sizeof(Node));
        if(temp == NULL)
            return NULL;
        temp->data = x;
        temp->next = NULL;
        return temp;
    }
    
    //入队
    void EnQueue(Queue * q,DataType x)
    {
        Node * temp = newNode(x);
        if (temp == NULL)
           {
               printf("memory alloctated failed.\n");
               exit(1);
               }
        if(q->rear == NULL)
        {
            q->front = q->rear = temp;
            return;
        }
        q->rear->next = temp;
        q->rear = temp;
    
    
    }
    
    //出队
    Node * DeQueue(Queue * q)
    {
        if (q->front == NULL)
            return NULL;
        Node * temp = q->front;
        q->front = q->front->next;
    
        if(q->front == NULL)
            q->rear = NULL;
        return temp;
    }
    
    //Driver Program to test anove functions
    
    int main(void)
    {
        Queue q;
        Initialize(&q);
        EnQueue(&q,10);
        EnQueue(&q,20);
        DeQueue(&q);
        DeQueue(&q);
        EnQueue(&q,30);
        EnQueue(&q,40);
        EnQueue(&q,50);
        Node * item = DeQueue(&q);
        if (item != NULL)
            printf("Dequeued item is %d",item->data);
        return 0;
    }
    

    相关文章

      网友评论

          本文标题:队列

          本文链接:https://www.haomeiwen.com/subject/uzjsextx.html