数据结构考研学习笔记（六）---栈和队列

你的名字 2023-03-13 06:59 4阅读 0赞

### 队列 ###

*  1. 队列的基本概念
 *   *  1.1 队列的定义
     *  1.2 队列常见的基本操作
 *  2. 队列的顺序存储结构
 *   *  2.1 队列的顺序存储
     *  2.2 循环队列
     *  2.3 循环队列操作
 *  3. 队列的链式存储结构
 *   *  3.1 队列的链式存储
 *  4. 双端队列

# 1. 队列的基本概念 #

## 1.1 队列的定义 ##

队列简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。向队列中插入元素称为**入队**或**进队**；删除元素称为**出队**或**离队**。操作特性：**先进先出**。

## 1.2 队列常见的基本操作 ##

InitQueue（&Q）：初始化队列，构造一个空队列Q。  
QueueEmpty（Q）：判断列空，若队列Q为空返回true，否则返回false。  
EnQueue（&Q，x）：入队，若队列Q未满，将x加入，使之称为新的队尾。  
DeQueue（&Q，&x）:出队，若队列Q非空，删除队头元素，并用x返回。  
GetHand（Q,&x）:读队头元素，若队列Q非空，则将队头元素赋值给x。

# 2. 队列的顺序存储结构 #

## 2.1 队列的顺序存储 ##

队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针front指向队头元素，队尾指针rear指向队尾元素。  
下面展示一些 `内联代码片`。

队列的顺序存储类型可描述为：

#define MaxSize 50					//定义队列中元素的最大个数
    typedef struct
    {
        
    	ElemType data[MaxSize];        //存放队列元素
    	int front,rear;                //队头指针和队尾指针
    }SqQueue;

初始状态（队空条件）：Q.frontQ.rear0.（不是充分必要条件）  
进队操作：队不满时，先送值到队尾元素，再将队尾指针加1.  
出队操作：对不空时，先取队头元素值，再将对头指针加1.  
队长条件：Q.rear - Q.front  
队满条件：假溢出问题

## 2.2 循环队列 ##

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

将顺序队列臆造为一个环状空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。当队首指针Q.front = MaxSize-1后，再前进一个位置就自动到0，这可以利用除法取余运算（%）来实现。  
初始时：Q.front = Q.rear = 0;  
队首指针进1：Q.front = （Q.front+1）% MaxSize。  
队尾指针进1：Q.rear = (Q.rear+1)%MaxSize.  
队列长度：（Q.rear +MaxSzie-Q.front）%MaxSize。  
出队入队时：指针都按顺时针方向进1。

## 2.3 循环队列操作 ##

1.初始化

void InitQueue(SqQueue &Q)
    {
        
    	Q.rear = Q.front = 0;;             //初始化队首、队尾指针
    }

2.判断空

bool isEmpty(SqQueue Q)
    {
        
    	if(Q.rear==Q.front)				//队空条件
    		return true;
    	else
    		return false;
    }

3.入队

bool EnQueue(SqQueue &Q, ElemType &x)
    {
        
    	if((Q.rear+1)%MaxSize==Q.front)//队满则报错
    		return false;
    	Q.data[Q.rear] = x;
    	Q.rear = (Q.rear+1)%MaxSize;//队尾指针加1取模
    	return true;
    }

4.出队

bool DeQueue(SqQueue &Q,ElemType &x)
    {
        
    	if(Q.rear==Q.front)
    		return false; 				//队空则报错
    	x=Q.data[Q.front];
    	Q.front =(Q.front+1)%MaxSize;		//队头指针加1取模
    	return true;
    }

# 3. 队列的链式存储结构 #

## 3.1 队列的链式存储 ##

队列的链式表示称为脸队列，它实际上是一个同时带有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点。  
![不带头结点的链式队列][20200512212137479.png]

typedef struct{
        					//链式队列结点
    	ElemType data;
    	struct LinkNode *next;
    }LinkNode;
    typedef struct{
        					//链式队列
    	LinkNode *front,*rear;		//队列的队头和队尾指针
    }LinkQueue;

判断空：

lvoid isEmpty (LinkQueue Q){
        
    if(Q.front == Q.rear)
    return true ;
    else
    return false;
    )

入队：

void EnQueue (LinkQueue &Q,ElemType x){
        
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode))
    s->data = x;
    s->next = NULL;
    Q.rear->next = s;
    Q.rear = s;
    )

出队：

bool DeQueue (LinkQueue &Q,ElemType &x){
        
    if(Q.front == Q.rear)
    	return false;
    LinkNode *p = Q.front->next;
    x = p->data;
    Q.front->next = p->next;
    if(Q.rear == p)
    	Q.rear = Q.front;
    free (p);
    return true;

# 4. 双端队列 #

双端队列是指允许两端都可以进行入队和出队操作的队列，。  
在双端队列进队时，前端进的元素排列在队列中后端进的元素的前面，后端进的元素排列在队列中前端进的元素的后面。在双端队列出队时，无论是前端还是后端出队，先出的元素排列在后出的元素的前面。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center]: /images/20230312/beafc3451b954b69b515eff55dda4999.png
[20200512212137479.png]: https://img-blog.csdnimg.cn/20200512212137479.png