数据结构与算法分析 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 — 双端队列的实现的详细内容...