数据结构之队列

素颜马尾好姑娘i 2022-04-22 13:06 194阅读 0赞

# 概念 #

可以把队列想象成排队买票，先来的人先买，后来的人站在队尾排队后买，不允许插队，先进者先出，这就是典型的“队列”。

# 特点 #

先进者先出，后进者后出，不允许在中间进行插入、删除操作。

# 基本操作 #

入队：在队列的末尾插入元素  
出队：在队列的头部取出元素

# 常见队列 #

普通队列、循环队列、阻塞队列、并发队列

# 队列的实现 #

数组实现：要注意选择数组的长度  
链表实现：无限长队列，可能会出现过长等待时间

# 循环队列的C语言实现(数组实现) #

#define MAXQSIZE 100
    typedef struct { 
      int * base;
      int front;
      int rear;
    }SqQueue;
    
    bool InitQueue(SqQueue &Q){ 
      Q.base = (int *)malloc(MAXQSIZE * sizeof(int));
      if(!Q.base)
        exit(OVERFLOW);
      Q.front = Q.rear = 0;
      return True;
    }
    
    int QueueLength(SqQueue Q){ 
      return (Q.rear - Q.front + MAXQSIZE) % MAXQIZE;
    }
    
    bool EnQueue(SqQueue &Q, int e){ 
      // Queue full
      if ((Q.rear + 1) % MAXQSIZE == Q.front)
        return ERROR;
      Q.base[Q.rear] = e;
      Q.rear = (Q.rear + 1) % MAXQSIZE;
      return True;
    }
    
    bool DeQueue(SqQueue &Q){ 
      if(Q.front == Q.rear)
        reuturn ERROR;
      Q.front = (Q.front+1) % MAXQSIZE;
      return True;
    }

# 队列的C语言实现（链表实现） #

#include<stdbool.h>
    
    typedef int datatype
    
    struct Node { 
     datatype data;
     struct Node *next;
    };
    
    typedef struct { 
     struct Node *front;
     struct Node *rear;
    } Boundary;
    
    void initQueue(Boundary border) { 
     border.front = border.rear = (struct Node*) malloc(sizeof(struct Node));
     if(!border.front) { 
      printf("no more memory");
      return;
     }
     border.rear->next = NULL;
     return;
    }
    
    bool empty(Boundary border) { 
     if(border.front == border.rear) { 
      printf("queue empty");
      return true;
     }else { 
      printf("queue not empty");
      return false;
     }
    }
    
    bool enQueue(datatype newData, Boundary border) { 
     newNode = (struct Node*) malloc(sizeof(struct Node));
     newNode->data = newData;
     newNode->next = NULL;
     border.rear->next = newNode;
     border.rear = newNode;
     return true
    }
    
    bool deQueue(Boundary border) { 
     if(border.front == border.rear) 
      return false;
     struct Node *deNode = border.front->next;
     border.front-next = deNode->next;
     if(border.rear == deNode)
       border.rear = border.front;
     free(deNode);
     return true;
    }
     free(deNode);
    }