数据结构与算法分析——C语言描述(第3章 表、栈和队列③)
2022/9/11 1:24:47
本文主要是介绍数据结构与算法分析——C语言描述(第3章 表、栈和队列③),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录- 3.4 队列(Queue)ADT
- 3.4.1 队列模型
- 3.4.2 队列的实现
- 3.4.2.1 队列的链表实现
- 3.4.2.2 队列的数组实现
- 3.4.3 队列的应用
3.4 队列(Queue)ADT
像栈一样,队列也是表。然而,使用队列时插入在一端进行而删除则在另一端进行。
3.4.1 队列模型
队列的基本操作:
- Enqueue(入队)——在表的末端(叫作队尾(rear))插入一个元素。
- Dequeue(出队)——删除(或返回)在表的开头(叫作队头(front))的元素.
3.4.2 队列的实现
像栈一样,对于队列而言,任何表的实现都是合法的,无论是链表实现还是数组实现对于每一种ADT操作都给出快速的\(O(1)\)运行时间。
3.4.2.1 队列的链表实现
队列ADT链表实现的类型声明:
#ifndef _Queue_h struct Node; struct QNode; typedef struct Node *PtrToNode; typedef struct QNode *Queue; int IsEmpty( Queue Q ); Queue CreateQueue( void ); void DisposeQueue( Queue Q ); void MakeEmpty( Queue Q ); void Enqueue( ElementType X, Queue Q ); ElementType Front( Queue Q ); void Dequeue( Queue Q ); ElementType FrontAndDequeue( Queue Q ); #endif /* _Queue_h */ /* Place in implementation file */ /* Stack implementation is a linked list */ struct Node { ElementType Element; PtrToNode Next; }; struct QNode { PtrToNode rear; PtrToNode front; };
具体函数实现:
/* Return true if Q is empty */ int IsEmpty( Queue Q ) { return Q->front == NULL; } /* Create an empty queue */ Queue CreateQueue( void ) { Queue Q; Q = malloc( sizeof( struct QNode ) ); if( Q == NULL ) FatalError( "Out of space!!!" ); Q->front = NULL; Q->rear = NULL; MakeEmpty( Q ); return Q; } /* Dispose Q */ void DisposeQueue( Queue Q ) { if( Q != NULL ) { MakeEmpty( Q ); free( Q ); } } /* Make Q empty*/ void MakeEmpty( Queue Q ) { if( Q == NULL ) Error( "Must use CreateQueue first" ); else while( !IsEmpty( Q ) ) Dequeue( Q ); } /* Enqueue */ void Enqueue( ElementType X, Queue Q ) { PtrToNode TmpCell; TmpCell = malloc( sizeof( struct Node ) ); if ( TmpCell == NULL ) FatalError( "Out of space!!!" ); TmpCell->Element = X; TmpCell->Next = NULL; if( Q->rear == NULL ) { Q->rear = TmpCell; Q->front = TmpCell; } else { Q->rear->Next = TmpCell; Q->rear = TmpCell; } } /* Return the front element */ ElementType Front( Queue Q ) { if( !IsEmpty( Q ) ) return Q->front->Element; Error( "Empty queue" ); return 0; } /* Dequeue */ void Dequeue( Queue Q ) { PtrToNode FrontCell; if( IsEmpty( Q ) ) Error( "Empty queue" ); else { FrontCell = Q->front; if( Q->front == Q->rear ) Q->front = Q->rear = NULL; else Q->front = Q->front -> Next; free( FrontCell ); } } /* Return the front element and Dequeue*/ ElementType FrontAndDequeue( Queue Q ) { ElementType X = 0; if( IsEmpty( Q ) ) Error( "Empty queue" ); else { X = Front( Q ); Dequeue( Q ); } return X; }
3.4.2.2 队列的数组实现
队列ADT数组实现的类型声明:
#ifndef _Queue_h struct QueueRecord; typedef struct QueueRecord *Queue; int IsEmpty( Queue Q ); int IsFull( Queue Q ); Queue CreateQueue( int MaxElements ); void DisposeQueue( Queue Q ); void MakeEmpty( Queue Q ); void Enqueue( ElementType X, Queue Q ); ElementType Front( Queue Q ); void Dequeue( Queue Q ); ElementType FrontAndDequeue( Queue Q ); #endif /* _Queue_h */ /* Place in implementation file */ /* Queue implementation is a dynamically allocated array */ #define MinQueueSize ( 5 ) struct QueueRecord { int Capacity; int Front; int Rear; int Size; ElementType *Array; };
具体函数实现:
/* Return true if Q is empty */ int IsEmpty( Queue Q ) { return Q->Size == 0; } /* Return true if Q is full */ int IsFull( Queue Q ) { return Q->Size == Q->Capacity; } /* Create an empty queue */ Queue CreateQueue( int MaxElements ) { Queue Q; if( MaxElements < MinQueueSize ) Error( "Queue size is too small" ); Q = malloc( sizeof( struct QueueRecord ) ); if( Q == NULL ) FatalError( "Out of space!!!" ); Q->Array = malloc( sizeof( ElementType ) * MaxElements ); if( Q->Array == NULL ) FatalError( "Out of space!!!" ); Q->Capacity = MaxElements; MakeEmpty( Q ); return Q; } /* Dispose Q */ void DisposeQueue( Queue Q ) { if( Q != NULL ) { free( Q->Array ); free( Q ); } } /* Make Q empty*/ void MakeEmpty( Queue Q ) { Q->Size = 0; Q->Front = 1; Q->Rear = 0; } /* Enqueue */ static int Succ( int Value, Queue Q ) { if( ++Value == Q->Capacity ) Value = 0; return Value; } void Enqueue( ElementType X, Queue Q ) { if( IsFull( Q ) ) Error( "Full queue" ); else { Q->Size++; Q->Rear = Succ( Q->Rear, Q ); Q->Array[ Q->Rear ] = X; } } /* Return the front element */ ElementType Front( Queue Q ) { if( !IsEmpty( Q ) ) return Q->Array[ Q->Front ]; Error( "Empty queue" ); return 0; } /* Dequeue */ void Dequeue( Queue Q ) { if ( IsEmpty( Q ) ) Error( "Empty queue" ); else { Q->Size--; Q->Front = Succ( Q->Front, Q ); } } /* Return the front element and Dequeue*/ ElementType FrontAndDequeue( Queue Q ) { ElementType X = 0; if( IsEmpty( Q ) ) Error( "Empty queue" ); else { Q->Size--; X = Q->Array[ Q->Front ]; Q->Front = Succ( Q->Front, Q ); } return X; }
注意:为避免已经有元素出队而导致的越界,我们让Front或Rear到达数组的尾端时绕回到开头,即循环数组(circular array)实现。
3.4.3 队列的应用
实际生活例子
排队论(queueing theory)
这篇关于数据结构与算法分析——C语言描述(第3章 表、栈和队列③)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-27文件掩码什么意思?-icode9专业技术文章分享
- 2024-12-27如何使用循环来处理多个订单的退款请求,代码怎么写?-icode9专业技术文章分享
- 2024-12-27VSCode 在编辑时切换到另一个文件后再切回来如何保持在原来的位置?-icode9专业技术文章分享
- 2024-12-27Sealos Devbox 基础教程:使用 Cursor 从零开发一个 One API 替代品 审核中
- 2024-12-27TypeScript面试真题解析与实战指南
- 2024-12-27TypeScript大厂面试真题详解与解析
- 2024-12-26怎么使用nsenter命令进入容器?-icode9专业技术文章分享
- 2024-12-26导入文件提示存在乱码,请确定使用的是UTF-8编码怎么解决?-icode9专业技术文章分享
- 2024-12-26csv文件怎么设置编码?-icode9专业技术文章分享
- 2024-12-25TypeScript基础知识详解