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

算法导论顺序循环队列

阅读量：4087 次

发布时间：2019-05-25

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

顺序循环队列

1.什么是队列？什么是顺序队列？

队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾，每次离开的成员总是队列头上的。队列的顺序存储结构称为顺序队列，顺序结构可以用数组来实现。

2.顺序队列的基本操作（伪代码）

队列具有两个指向，一个是头指向（head），一个是尾指向（tail）。初始化的时候，头尾指向都指向同一个元素，元素入队列称为ENQUEUE，元素出队列称为DEQUEUE。下面的伪代码中，省略了对上溢和下溢的检查。

ENQUEUE(Q,x)
Q[Q.tail] = xif Q.tail == Q.length        Q.tail = 1else Q.tail = Qtail + 1
DEQUEUE(Q)
x = Q[Q.head]if Q.head = Q.length        Q.head = 1else Q.head = Q.head + 1return x

3.顺序队列的实现（C++）

实现部分对伪代码进行了一些改进：

对+1操作或-1操作后的数进行取余，使得队列方便地实现了首尾循环。

当Q.head == Q.tail + 1时，得出队列已满，防止上溢。

当Q.head == Q.tail时，得出队列为空，防止下溢。

//SequeQueue.h#pragma once#include 
   
    template
    
     class SequeQueue{public:    SequeQueue(unsigned int size);    bool DeQueue(ElemType* elem);    bool EnQueue(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 SequeQueue
      
       ::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 SequeQueue
        
         ::Empty(){ return (m_head == m_tail) ? true : false;}template
         
          bool SequeQueue
          
           ::EnQueue(ElemType elem){ if ( (m_tail + 1) % m_size == m_head) { assert(false && "Error: SequeQueue is overflow!"); return false; } else { m_array[m_tail] = elem; m_tail = (m_tail + 1) % m_size; return true; }}template
           
            bool SequeQueue
            
             ::DeQueue(ElemType* elem){ if (Empty()) { assert(false && "Error: SequeQueue is underflow!"); return false; } else { *elem = m_array[m_head]; m_head = (m_head + 1) % m_size; return true; }}template
             
              SequeQueue
              
               ::SequeQueue(unsigned int size) :m_array(new ElemType[size]),m_tail(0),m_head(0),m_size(size){ memset(m_array,0,sizeof(ElemType)*size);}

//main.cpp#include "Util.h"#include "SequeQueue.h"#include 
   
    using namespace std;typedef int ElemType;int main(){    const int QUEUE_SIZE = 10;    SequeQueue
    
      testSequeQueue(QUEUE_SIZE);    Util::PrintMemory(testSequeQueue,QUEUE_SIZE);    cout << "SequeQueue is " << (testSequeQueue.Empty() ? "Empty." : "Not Empty.") << endl;    for (int i = 1; i != 10; i++)    {        testSequeQueue.EnQueue(i);        cout << "\nEnQueue:" << i << endl;        Util::PrintMemory(testSequeQueue,QUEUE_SIZE);        cout << "SequeQueue is " << (testSequeQueue.Empty() ? "Empty." : "Not Empty.") << endl;    }    for (int i = 1; i != 5; i++)    {        int tempElem;        testSequeQueue.DeQueue(&tempElem);        cout << "\nDeQueue:" << tempElem << endl;        Util::PrintMemory(testSequeQueue,QUEUE_SIZE);        cout << "SequeQueue is " << (testSequeQueue.Empty() ? "Empty." : "Not Empty.") << endl;    }    for (int i = 1; i != 5; i++)    {        testSequeQueue.EnQueue(i);        cout << "\nEnQueue:" << i << endl;        Util::PrintMemory(testSequeQueue,QUEUE_SIZE);        cout << "SequeQueue is " << (testSequeQueue.Empty() ? "Empty." : "Not Empty.") << endl;    }    return 0;}