算法导论顺序循环双向队列-白红宇

算法导论顺序循环双向队列

阅读量：4089 次

发布时间：2019-05-25

本文共 5667 字，大约阅读时间需要 18 分钟。

顺序循环双向队列

1. 什么是双向队列？

算法导论原题：
10.1-5
Whereas a stack allows insertion and deletion of elements at only one end, and a queue allows insertion at one end and deletion at the other end, a deque (double-ended queue) allows insertion and deletion at both ends. Write four O(1) time procedures to insert elements into and delete elements from both ends of a deque implemented by an array.
译：栈只允许在一端插入和删除元素，队列只允许在一端插入和在另一端删除，一个deque（double-ended queue，双向队列）允许在两端插入和删除。写出4个运行时间为O(1)的过程，分别在两端插入和删除元素，该列队是用一个数组实现的。

2. 双向队列如何实现？

顺序双向循环队列只是在原来的顺序循环队列基础上，增加了队列头的插入和队列尾的删除操作。只要写过普通队列的操作，双向队列的操作也是不难写的，并没有多大难度。建议读者们自己尝试动手写一下。

3. 双向队列的实现（C++代码）

//SequeDeQueue.h#pragma once#include 
   
    template
    
     class SequeDeQueue{public:    SequeDeQueue(unsigned int size);    bool HeadDeQueue(ElemType* elem);    bool TailDeQueue(ElemType* elem);    bool HeadEnQueue(const ElemType& elem);    bool TailEnQueue(const ElemType& elem);    bool Empty();    bool Visit(ElemType* elem, unsigned int pos) const;private:    ElemType* m_array;    unsigned int m_tail;    unsigned int m_head;    unsigned int m_size;};template
     
      bool SequeDeQueue
      
       ::TailEnQueue(const ElemType& elem){    if ( (m_tail + 1 + m_size) % m_size == m_head)    {        assert(false && "Error: SequeDeQueue is overflow!");        return false;    }    else    {        m_array[m_tail] = elem;        m_tail = (m_tail + 1 + m_size) % m_size;        return true;    }}template
       
        bool SequeDeQueue
        
         ::HeadEnQueue(const ElemType& elem){ if ( (m_head - 1 + m_size) % m_size == m_head) { assert(false && "Error: SequeDeQueue is overflow!"); return false; } else { m_array[m_head] = elem; m_head = (m_head - 1 + m_size) % m_size; return true; }}template
         
          bool SequeDeQueue
          
           ::TailDeQueue(ElemType* elem){ if (Empty()) { assert(false && "Error: SequeDeQueue is underflow!"); return false; } else { m_tail = (m_tail - 1 + m_size) % m_size; *elem = m_array[m_tail]; return true; }}template
           
            bool SequeDeQueue
            
             ::HeadDeQueue(ElemType* elem){ if (Empty()) { assert(false && "Error: SequeDeQueue is underflow!"); return false; } else { m_head = (m_head + 1 + m_size) % m_size; *elem = m_array[m_head]; return true; }}template
             
              bool SequeDeQueue
              
               ::Visit(ElemType* elem, unsigned int pos) const{ if (pos >= m_size || pos < 0) { assert(false && "Error: Visit Pos is out range of array!"); return false; } *elem = m_array[pos]; return true;}template
               
                bool SequeDeQueue
                
                 ::Empty(){ return ((m_head + 1 + m_size) % m_size == m_tail) ? true : false;}template
                 
                  SequeDeQueue
                  
                   ::SequeDeQueue(unsigned int size) :m_array(new ElemType[size]),m_tail(0),m_head(size-1),m_size(size){ memset(m_array,0,sizeof(ElemType)*size);}

//Util.h#pragma oncenamespace Util{    template
   
        void PrintMemory(const T& dateStruct, unsigned int size)    {        cout << "PrintMemory: ";        for (int i = 0; i != size; i++)        {            ElemType tempElem;            dateStruct.Visit(&tempElem,i);            printf("%d ",tempElem);        }        printf("\n");        printf("\n");    }}

//main.cpp#include "Util.h"#include "SequeDeQueue.h"#include 
   
    using namespace std;typedef int ElemType;int main(){    const int QUEUE_SIZE = 10;    SequeDeQueue
    
      testSequeDeQueue(QUEUE_SIZE);    cout << "testSequeDeQueue is " << (testSequeDeQueue.Empty() ? "Empty." : "Not Empty.") << endl;    Util::PrintMemory(testSequeDeQueue,QUEUE_SIZE);    for (int i = 1; i != 4; i++)    {        testSequeDeQueue.HeadEnQueue(i);        cout << "HeadEnQueue:" << i << endl;        cout << "testSequeDeQueue is " << (testSequeDeQueue.Empty() ? "Empty." : "Not Empty.") << endl;        Util::PrintMemory(testSequeDeQueue,QUEUE_SIZE);    }    for (int i = 4; i != 7; i++)    {        testSequeDeQueue.TailEnQueue(i);        cout << "TailEnQueue:" << i << endl;        cout << "testSequeDeQueue is " << (testSequeDeQueue.Empty() ? "Empty." : "Not Empty.") << endl;        Util::PrintMemory(testSequeDeQueue,QUEUE_SIZE);    }    for (int i = 0; i != 2; i++)    {        ElemType tempElem;        testSequeDeQueue.HeadDeQueue(&tempElem);        cout << "HeadDeQueue:" << tempElem << endl;        cout << "testSequeDeQueue is " << (testSequeDeQueue.Empty() ? "Empty." : "Not Empty.") << endl;        Util::PrintMemory(testSequeDeQueue,QUEUE_SIZE);    }    for (int i = 0; i != 4; i++)    {        ElemType tempElem;        testSequeDeQueue.TailDeQueue(&tempElem);        cout << "TailDeQueue:" << tempElem << endl;        cout << "testSequeDeQueue is " << (testSequeDeQueue.Empty() ? "Empty." : "Not Empty.") << endl;        Util::PrintMemory(testSequeDeQueue,QUEUE_SIZE);    }    return 0;}

4. 程序运行结果

testSequeDeQueue is Empty.
PrintMemory: 0 0 0 0 0 0 0 0 0 0

HeadEnQueue:1
testSequeDeQueue is Not Empty.
PrintMemory: 0 0 0 0 0 0 0 0 0 1

HeadEnQueue:2
testSequeDeQueue is Not Empty.
PrintMemory: 0 0 0 0 0 0 0 0 2 1

HeadEnQueue:3
testSequeDeQueue is Not Empty.
PrintMemory: 0 0 0 0 0 0 0 3 2 1

TailEnQueue:4
testSequeDeQueue is Not Empty.
PrintMemory: 4 0 0 0 0 0 0 3 2 1

TailEnQueue:5
testSequeDeQueue is Not Empty.
PrintMemory: 4 5 0 0 0 0 0 3 2 1

TailEnQueue:6
testSequeDeQueue is Not Empty.
PrintMemory: 4 5 6 0 0 0 0 3 2 1

HeadDeQueue:3
testSequeDeQueue is Not Empty.
PrintMemory: 4 5 6 0 0 0 0 3 2 1

HeadDeQueue:2
testSequeDeQueue is Not Empty.
PrintMemory: 4 5 6 0 0 0 0 3 2 1

TailDeQueue:6
testSequeDeQueue is Not Empty.
PrintMemory: 4 5 6 0 0 0 0 3 2 1

TailDeQueue:5
testSequeDeQueue is Not Empty.
PrintMemory: 4 5 6 0 0 0 0 3 2 1

TailDeQueue:4
testSequeDeQueue is Not Empty.
PrintMemory: 4 5 6 0 0 0 0 3 2 1

TailDeQueue:1
testSequeDeQueue is Empty.
PrintMemory: 4 5 6 0 0 0 0 3 2 1