首页 > 代码库 > 数据结构与算法分析 3.26 — 双端队列的实现
数据结构与算法分析 3.26 — 双端队列的实现
一、题目
编写支持双端队列的例程，插入与弹出操作均花费 O(1)时间
二、解答
双端队列（deque，全名double-ended queue）是一种具有队列和栈性质的数据结构。
双端队列中的元素可以从两端弹出，插入和删除操作限定在队列的两边进行。
基本操作：在双端队列两端插入与删除。
ADT术语：
Capacity：数组容量
Left：队列左端，指向队列左边第一个元素
Right：队列右端，指向队列右边最后一个元素的下一个位置
初始化：Left = Right = 0；
判空： Left = Right
判满： (Left - 1) % Capacity == Right
三、代码
struct DequeRecord;typedef struct DequeRecord *Deque;struct DequeRecord{ int Capacity; int Left; int Right; ElementType *Array;};Deque CreateDeque( int MaxElements );int IsEmpty( Deque D );int IsFull( Deque D );void MakeEmpty( Deque D );void Push_Left( ElementType X, Deque D );void Push_Right( ElementType X, Deque D );ElementType Pop_Left( Deque D );ElementType Pop_Right( Deque D );void DisposeDeque( Deque D );Deque CreateDeque( int MaxElements ){ Deque D; D = (Deque)malloc( sizeof(struct DequeRecord) ); if ( D == NULL ) { printf( "Out of space" ); return NULL; } D->Array = (ElementType *)malloc( sizeof(ElementType) * MaxElements ); if ( D->Array == NULL ) { printf( "Out of space" ); return NULL; } D->Capacity = MaxElements; MakeEmpty( D ); return D;}int IsEmpty( Deque D ){ return D->Left == D->Right;}int IsFull( Deque D ){ return ( D->Left + D->Capacity - 1 ) % D->Capacity == D->Right;}void MakeEmpty( Deque D ){ D->Left = 0; D->Right = 0;}void Push_Left( ElementType X, Deque D ){ if ( IsFull(D) ) printf( "Full deque" ); else { D->Left = ( D->Left - 1 + D->Capacity ) % D->Capacity; D->Array[D->Left] = X; }}void Push_Right( ElementType X, Deque D ){ if ( IsFull(D) ) printf( "Full deque" ); else { D->Array[D->Right] = X; D->Right = ( D->Right + 1 ) % D->Capacity; }}ElementType Pop_Left( Deque D ){ ElementType TmpCell; if ( IsEmpty(D) ) { printf( "Empty deque" ); return 0; // 应该返回无效元素 } else { TmpCell = D->Array[D->Left]; D->Left = ( D->Left + 1 ) % D->Capacity; } return TmpCell;}ElementType Pop_Right( Deque D ){ ElementType TmpCell; if ( IsEmpty(D) ) { printf( "Empty Deque" ); return 0; } else { D->Right = ( D->Right - 1 + D->Capacity ) % D->Capacity; TmpCell = D->Array[D->Right]; } return TmpCell;}void DisposeDeque( Deque D ){ if ( D != NULL ) { free( D->Array ); free( D ); }}
数据结构与算法分析 3.26 — 双端队列的实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。