队列（从数据结构的三要素出发）

2024-05-28 1046阅读

文章目录

  • 存储结构
  • 物理结构
    • 顺序队列
    • 循环队列
    • 链式队列
    • 双端队列
    • 数据的操作
      • 顺序队列的基本操作
      • 循环队列的基本操作
      • 链式队列的基本操作
      • 双端队列的基本操作
      • 数据结构的应用
        • 队列在层次遍历中的应用
        • 队列在计算机系统中的应用（OS）

          存储结构

          队列是只允许在一端进行插入，在另一端进行删除操作的线性表。

          队列（从数据结构的三要素出发）

          物理结构

          顺序队列

          利用静态数组实现，并需要记录队头和队尾指针，且队列的大小不可改变。

          typedef struct {
	int data;			// 数据域
	int front, rear;	// 队头队尾指针域
} SqQueue;

          队列（从数据结构的三要素出发）

          在图d队列中，仅有一个元素。这时入队出现“上溢出”,但这种溢出并不是真正的溢出，在data 数组中依然存在可以存放元素的空位置，所以是一种 “假溢出”，极大的浪费了存储空间以及大小不可扩充的问题 。

          循环队列

          为了解决 “假溢出” 的问题，我们引入循环队列。将顺序队列想象成一个环状的空间，将存储队列从逻辑上视为一个环，称之为循环队列。

          队列（从数据结构的三要素出发）

          定义与顺序队列一样，区别在于判满和判空的逻辑不同。解决了“假溢出”的问题，但是没有解决队列不可扩充的问题。

          链式队列

          利用单链表实现，需要头指针和队尾指针，解决了顺序队列中队列的大小不可扩充的问题。

          队列（从数据结构的三要素出发）

          定义结点

          typedef struct LinkNode {
	int data;					// 数据域
	struct LinkNode *next;		// 指针域
} LinkNode;

          定义队列

          typedef struct {
	LinkNode *front, *rear;		// 定义队头队尾指针
} LinkQueue;

          双端队列

          双端队列是指允许两端都可以进行插入和删除操作的线性表，双端队列两端的地位是平等的，为了方便理解，将左端也视为前端，右端也视为后端。

          队列（从数据结构的三要素出发）

          链式存储

          typedef struct DequeNode {			// 定义双端队列结点
	int data;						// 数据域
	struct DequeNode *pre, *next;	// 前后指针域
} DequeNode;
typedef struct {					// 定义双端队列
	DequeNode *front, *rear;		// 头尾指针域
} Deque;

          数据的操作

          顺序队列的基本操作

          初始化

          void InitQueue(SqQueue &q)
{
	q.front = q.rear = 0;
}

          判断队列为空

          bool isEmpty(SqQueue q)
{
	if (q.front == q.rear) return true;
	return false;
}

          判断队列为满

          bool isFull(SqQueue q) 
{
	if (q.rear == Maxsize) return true;
	return false;
}

          入队列

          bool EnQueue(SqQueue &q, int &x)
{
	if (!isFull(q))
	{
		q.data[q.rear ++ ] = x;
		return true;
	}
	return false;
}

          出队列

          bool DeQueue(SqQueue &q, int &x)
{
	if (!isEmpty(q))
	{
		x = q.data[q.front ++ ];
		return true;
	}
	return false;
}

          循环队列的基本操作

          初始化

          void InitQueue(SqQueue &q)
{
	q.rear = q.front = 0;
}

          判空/判满/入队/出队（三种处理方式）

          若用循环队列的话，判断队空的条件是Q.front==Q.rear，判断队满的条件也是Q.front==Q.rear。这就会区分不出来到底是队空还是队满。

          为了区分是队空还是队满的情况，有三种处理方式：

          • 牺牲一个单元来区分队空和队满，入队时少用一个队列单元，约定以“队头指针在队尾指针的下一位置作为队满的标志”。 
            bool isEmpty(SqQueue q)
{
	if (q.rear == q.front) return true;
	return false;
} 
bool isFull(SqQueue q)
{
	if ((q.rear + 1) % Maxsize == q.front) return true;
	return false;
}
bool EnQueue(SqQueue &q, int x)
{
	if (!isFull(q))
	{
		q.data[q.rear] = x;
		q.rear = (q.rear + 1) % Maxsize;
		return true;
	}
	return false;
}
bool DeQueue(SqQueue &q, int &x)
{
	if (!isEmpty(q))
	{
		x = q.data[q.front];
		q.front = (q.front + 1) % Maxsize;
		return true;
	}
	return false;
}
            • 类型中增设size数据成员，表示元素个数。 
              typedef struct {
	int data[Maxsize];			// 数据域
	int front, rear;			// 队头队尾指针域
	int size;					// 队中元素个数
} SqQueue;
void InitQueue(SqQueue &q)
{
	q.front = q.rear = 0;
	q.size = 0;
}
bool isEmpty(SqQueue q)
{
	if (q.size == Maxsize) return true;
	return false;
}
bool isFull(SqQueue q)
{
	if (q.size == 0) return true;
	return false;
}
bool EnQueue(SqQueue &q, int x)
{
	if (!isFull(q))
	{
		q.data[q.rear] = x;
		q.rear = (q.rear + 1) % Maxsize;
		q.size ++ ;
		return true;
	}
	return false;
}
bool DeQueue(SqQueue &q, int &x)
{
	if (!isFull(q))
	{
		x = q.data[q.front];
		q.front = (q.front + 1) % Maxsize;
		q.size -- ;
		return true;
	}
	return false;
}
              • 类型中增设 tag 数据成员，以区分是队满还是队空。删除成功置 tag=0,插入成功置 tag=1。只有删除操作才能使得队空，只有插入操作才能使得队满。 
                typedef struct {
	int data[Maxsize];			// 数据域
	int front, rear;			// 队头队尾指针
	int tag;					// 标志域
} SqQueue;
void InitQueue(SqQueue &q)
{
	q.front = q.rear = 0;
	q.tag = 0;
}
bool isEmpty(SqQueue q)
{
	if (q.rear == q.front && tag == 0) return true;
	return false;
}
bool isFull(SqQueue q)
{
	if (q.rear == q.front && tag == 1) return true;
	return false;
}
bool EnQueue(SqQueue &q, int x)
{
	if (!isFull(q, x))
	{
		q.data[q.rear] = x;
		q.rear = (q.rear + 1) % Maxsize;
		q.tag = 1;
		return true;
	}
	return false;
}
bool DeQueue(SqQueue &q, int &x)
{
	if (!isEmpty(q))
	{
		x = q.data[q.front];
		q.front = (q.front + 1) % Maxsize;
		q.tag = 0;
		return true;
	}
	return false;
}

                链式队列的基本操作

                初始化

                void InitQueue(LinkQueue &q)
{
	q.rear = q.front = (LinkNode *) malloc (sizeof(LinkNode));
	q.front->next = NULL;
}

                判空

                bool isEmpty(LinkQueue q)
{
	if (q.front == q.rear) return true;
	return false;
}

                入队

                bool EnQueue(LinkQueue &q, int x)
{
	LinkNode *t = (LinkNode *) malloc (sizeof(LinkNode));
	t->data = x;
	t->next = NULL;
	q.rear->next = t;
	q.rear = t;
	return true;
}

                出队

                bool DeQueue(LinkQueue &q, int &x)
{
	if (!isEmpty(q))
	{	
		LinkNode *t = q.front->next;
		x = t->data;
		q.front->next = t->next;
		if (q.rear == t) 				// 若只有一个结点，删除后使其变为空队列
			q.rear = q.front;		
		free(t);
		return true;
	}
	return false;
}

                双端队列的基本操作

                初始化

                void InitQueue(Deque &q)
{
	q.front = q.rear = NULL;
}

                判空

                bool isEmpty(Deque q)
{
	if (q.front == NULL && q.rear == NULL) return true;
    return false;
}

                队头插入

                bool InsertFront(Deque &q, int x)
{
	DequeNode *newNode = (DequeNode *) malloc(sizeof(DequeNode));
	newNode->data = x;
    newNode->pre = NULL;
    newNode->next = q->front;
	if (isEmpty(q)) 
        q->rear = newNode;
    else
        q->front->pre = newNode;
  
    q->front = newNode;
    return true;
}

                队尾插入

                bool InsertRear(Deque &q, int x)
{
	DequeNode *newNode = (DequeNode *) malloc(sizeof(DequeNode));
	newNode->data = x;
    newNode->next = NULL;
    newNode->pre = q->rear;
	
	if (isEmpty(q)) 
        q->front = newNode;
    else 
        q->rear->next = newNode;
   
    q->rear = newNode;
    return true;
}

                队头删除

                bool DeleteFront(Deque &q, int &x)
{
	if (isEmpty(q)) return false;
	DequeNode *temp = q->front;
    x = temp->data;
    q->front = q->front->next;
	if (q->front)				// 如果队列不为空，更新新的队首节点的 prev 指针
        q->front->prev = NULL;
    else						// 如果删除后队列为空，更新队尾指针
        q->rear = NULL;
   
    free(temp);
    return true;
}

                队尾删除

                bool DeleteRear(Deque &q, int &x)
{
	if (isEmpty(q)) return false;
    DequeNode *temp = q->rear;
    x = temp->data;
    q->rear = q->rear->prev;
    if (q->rear)       				// 如果队列不为空，更新新的队尾节点的 next 指针
        q->rear->next = NULL;
    else 							// 如果删除后队列为空，更新队首指针
        q->front = NULL;
   
    free(temp);
    return true;
}

                数据结构的应用

                队列在层次遍历中的应用

                队列适用于逐层或逐行处理，使用队列是为了保存下一步的处理顺序。下面用二叉树(见图 3.17)层次遍历的例子，说明队列的应用。

                队列（从数据结构的三要素出发）

                该过程的简单描述如下：

                ① 根结点入队，

                ② 若队空(所有结点都已处理完毕),则结束遍历；否则重复③操作。

                ③队列中第一个结点出队，并访问之。若其有左孩子，则将左孩子入队；若其有右孩子，则将右孩子入队，返回②。

                void InverLevel(BiTree T)
{
	SqQueue q, InitQueue(q);
	BiTNode *p = T;				// 遍历指针
	EnQueue(q, p);
	while (!isEmpty(q))
	{	
		DeQueue(q, p);
		visit(p);
		if (p->lchild) Enqueue(q, p->lchild);
		if (p->rchild) Enqueue(q, p->rchild);
	}
}

                队列在计算机系统中的应用（OS）

                缓冲区的逻辑结构：

                主机输出数据给打印机打印，输出数据的速度比打印数据的速度要快得多，因为速度不匹配，若直接把输出的数据送给打印机打印，则显然是不行的。解决的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依次写入这个缓冲区，写满后就暂停输出，转去做其他的事情。打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求。主机接到请求后再向缓冲区写入打印数据。这样做既保证了打印数据的正确，又使主机提高了效率。由此可见，打印数据缓冲区中所存储的数据就是一个队列。

                队列出队入队操作的应用：

                CPU资源的竞争就是一个典型的例子。在一个带有多终端的计算机系统上，有多个用户需要CPU各自运行自己的程序，它们分别通过各自的终端向操作系统提出占用CPU 的请求。操作系统通常按照每个请求在时间上的先后顺序，把它们排成一个队列，每次把CPU分配给队首请求的用户使用。当相应的程序运行结束或用完规定的时间间隔后，令其出队，再把CPU 分配给新的队首请求的用户使用。这样既能满足每个用户的请求，又使CPU能够正常运行。

VPS购买请点击我

免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们，邮箱：ciyunidc@ciyunshuju.com。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!

相关阅读

目录[+]