数据结构-队列之顺序队列

分手后的思念是犯贱 2022-05-04 00:26 277阅读 0赞

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。  
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

顺序队列是指分配一块连续的存储单元存放队列中的元素，并附设两个指针front和rear分别指示队头元素和队尾元素的位置。

队头指针指向队头元素，队尾指针指向队尾元素的下一个位置。

//队列之顺序队列
    
    #include "stdafx.cpp"
    
    #define ElementType int 
    #define MaxSize 50
    typedef struct {
    	ElementType data[MaxSize]; //存放队列的元素
    	int front, rear; //队头指针和队尾指针
    	int count;//统计元素个数
    }SeQueue;
    
    /*
    初始化空队列
    */
    void InitQueue(SeQueue &q) {
    	q.front = q.rear = 0;
    	q.count = 0;
    }
    /*
    判断队列是否为空
    count==0 || q.front == q.rear ==0
    */
    bool QueueEmpty(SeQueue q) {
    	if (q.count <= 0) {
    		return true;
    	}
    	return false;
    }
    
    /*
    入队操作
    1.判断队列是否已满
    2.赋值给队尾，队尾指针+1
    */
    bool EnQueue(SeQueue &q,ElementType e) {
    	//判断是否已满：尾指针-头指针
    	if (q.count >= MaxSize) {
    		return false;
    	}
    	q.data[q.rear] = e;
    	q.rear++;
    	q.count++;
    	return true;
    }
    
    /*
    出队操作
    1.判断队列是否为空
    2.取出队头元素，队头指针+1
    */
    ElementType DeQueue(SeQueue &q) {
    	if (QueueEmpty(q)) {
    		return NULL;
    	}
    	ElementType e = q.data[q.front];
    	q.front++;
    	q.count--;
    	return e;
    }