【数据结构——队列篇(C描述）】

左手的ㄟ右手 2022-12-13 10:00 213阅读 0赞

### 【数据结构——队列(C描述）】 ###

*  一、队列的顺序表示
 *   *  （一）队列的进队和出队演示
     *  （二）存在的问题
     *  （三）解决办法
     *  （四）循环队列
     *   *  1、循环队列初始化
         *  2、循环队列入队
         *  3、循环队列出队
 *  二、链队
 *   *  （一）链队的表示
     *   *  1、队列的链式存储结构
         *  2、队列运算指针变化状况
     *  （二）链队的基本操作
     *   *  1、链队的初始化
         *  2、链队的入队
         *  3、链队的出队

# 一、队列的顺序表示 #

## （一）队列的进队和出队演示 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 1]

## （二）存在的问题 ##

**设当前队列分配的最大空间为MAXSIZE,则：**  
**当Q.front = 0时且Q.rear = MAXSIZE时，若再有元素入队，会发生溢出——真溢出。**  
![在这里插入图片描述][20201010205719410.png_pic_center]  
**当Q.front != 0是且Q.rear = MAXSIZE时，若再有元素入队，会发生溢出——假溢出。**  
![在这里插入图片描述][20201010205850420.png_pic_center]  
**循环队列基本思想：把队列设想成一个环形，即：Q.base\[0\]接在Q.base\[MAXSIZE-1\]之后，若Q.rear=MAXSIZE,则令 Q.rear=0.**

## （三）解决办法 ##

**将顺序队列变为一个环状的空间**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 2]

//入队
    Q.base[Q.rear] = x;
    Q.rear = (Q.rear + 1) % MAXSIZE;
    //队满判定条件
    (Q.rear + 1) % MAXSIZE == Q.front(少用一存储单元)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 3]

//出队
    x = Q.base[Q.front];
    Q.front = (Q.front + 1) % MAXSIZE;
    //队空判定条件
    Q.rear == Q.front;

## （四）循环队列 ##

### 1、循环队列初始化 ###

#define MAXQSIZE 100
    typedef struct
    {
        
    	QElemType* base;
    	int front;
    	int rear;
    }SqQueue;
    
    Status InitQueue(SqQueue& Q)
    {
        
    	Q.base = new QElemType[MASQSIZE];//开辟空间
    	if (!Q.base) exit(OVERFLOW);//存储分配失败
    	Q.front = Q.rear = 0;
    	return OK;
    }

### 2、循环队列入队 ###

Status EnQueue(SqQueue& Q, QElemType e)
    {
        
    	if ((Q.rear + 1) % MAXQSIZE == Q.front)
    		return ERROR;//队满
    	Q.base[Q.rear] = e;
    	Q.rear = (Q.rear + 1) % MAXQSIZE;
    	return OK;
    }

### 3、循环队列出队 ###

Status DeQueue(SqQueue& Q, QElemType& e)
    {
        
    	if (Q.front == Q.rear)
    		return ERROR;//队空
    	e = Q.base[Q.front];
    	Q.front = (Q.front + 1) % MAXQSIZE;
    	return OK;
    }

# 二、链队 #

## （一）链队的表示 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 4]

### 1、队列的链式存储结构 ###

typedef struct QNode
    {
        
    	QElemType data;
    	struct QNode* next;
    }QNode,*QueuePtr;
    typedef struct
    {
        
    	QueuePtr front;//队头指针
    	QueuePtr rear;//队尾指针
    }LinkQueue;

### 2、队列运算指针变化状况 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 5]

## （二）链队的基本操作 ##

### 1、链队的初始化 ###

Status InitQueue(LinkQueue& Q)
    {
        
    	Q.front = Q.rear = new QNode;
    	if(!Q.front) exit(OVERFLOW);
    	Q.front->next = NULL;
    	return OK;
    }

### 2、链队的入队 ###

![在这里插入图片描述][20201010231918906.png_pic_center]

Status EnQueue(LinkQueue& Q, QElemType e)
    {
        
    	p = new QNode;
    	if (!p) exit(OVERFLOW);//存储分配失败
    	p->data = e;
    	p->next = NULL;
    	Q.rear->next = p;
    	Q.rear = p;
    	return OK;
    }

### 3、链队的出队 ###

![在这里插入图片描述][20201010232128403.png_pic_center]

Status DeQueue(LinkQueue& Q, QElemType& e)
    {
        
    	if (Q.front == Q.rear)
    		return ERROR;//队列为空
    	p = Q.front->next;//p指向队头元素
    	e = p->data;//e保存队头元素的值
    	Q.front->next = p->next;//修改头指针
    	if (Q.rear == p)
    		Q.rear = Q.front;//如果最后一个元素被删，则队尾指针指向头结点
    	delete p;//释放原队头元素的空间
    	return OK;
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/7b42d909866c44b0bc6178682f100342.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/5c6379d805fb4b01ba3411aff136aeed.png
[20201010205719410.png_pic_center]: /images/20221123/e6e0189ac53c4b50a5da65754d00c8bc.png
[20201010205850420.png_pic_center]: /images/20221123/a7adb81e578446809f9c781d8593f190.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/f59d287516fd4d23a2aac9a6641aa2ba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/61be81ecc9194f1c94a2128f8b56089b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/66102300d0444a21b852ffdb32a77954.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/85009f30af714247b2df9a7bc35df3df.png
[20201010231918906.png_pic_center]: /images/20221123/857a885c323d44849a91bec30df0bcf0.png
[20201010232128403.png_pic_center]: /images/20221123/7596f1c7922f477489fe487f626b7d37.png