一、概念

队列(Queue)：也是运算受限的线性表。是一种先进先出(FirstIn FirstOut ，简称FIFO)的线性表。只允许在表的一端进行插入，而在另一端进行删除。

队首(front)：允许进行删除的一端称为队首。

队尾(rear)：允许进行插入的一端称为队尾。

例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。

队列中没有元素时称为空队列。在空队列中依次加入元素a1, a2, …, an之后，a1是队首元素，an是队尾元素。显然退出队列的次序也只能是a1, a2, …, an，即队列的修改是依先进先出的原则进行的，如图3-5所示。

二、队列的抽象数据类型定义

< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PHByZSBjbGFzcz0="brush:java;">ADT Queue{ 数据对象：D ={ ai|ai∈ElemSet, i=1, 2, …, n, n >= 0 } 数据关系：R = { | ai-1, ai∈D, i=2,3,…,n } 约定a1端为队首，an端为队尾。基本操作： Create()：创建一个空队列； EmptyQue()：若队列为空，则返回true ，否则返回flase ； InsertQue(x) ：向队尾插入元素x； DeleteQue(x) ：删除队首元素x； } ADT Queue

三、代码实现:

Queue.h

#ifndef __CHelloWorld__Queue__
#define __CHelloWorld__Queue__

#include 
  
   
#include 
   
     #include 
    
      using namespace std; #define QUEUELEN 15 typedef struct { char name[10]; //结点的关键字 int age; }DATA; typedef struct { DATA data[QUEUELEN]; int head; int tail; }SQType; class Queue { public: bool init(); static Queue * create(void); SQType *SQTypeInit(); //队列初始化 int SQTypeIsEmpty(SQType *q); //判断空队列 int SQTypeIsFull(SQType *q); //清空满队列 void SQTypeClear(SQType *q); //清空队列 void SQTypeFree(SQType *q); //释放队列 int InSQType(SQType *q,DATA data);//入队 DATA *OutSQType(SQType *q); //出队 DATA *PeekSQType(SQType *q); //读结点 int SQLTypeLen(SQType *q); //计算队列长度 }; #endif /* defined(__CHelloWorld__Queue__) */

Queue.cpp

#include "Queue.h"

SQType *Queue::SQTypeInit()
{
    SQType *q;
    if (q = (SQType*)malloc(sizeof(SQType)))
    {
        q->head = 0;
        q->tail = 0;
        return q;
    }
    else
    {
        return NULL;
    }
}

int Queue::SQTypeIsEmpty(SQType *q)
{
    int temp;
    temp = q->head == q->tail;
    return (temp);
}

int Queue::SQTypeIsFull(SQType *q)
{
    int temp;
    temp = q->tail == QUEUELEN;
    return (temp);
}

void Queue::SQTypeClear(SQType *q)
{
    q->head = 0;
    q->tail = 0;
}

void Queue::SQTypeFree(SQType *q)
{
    if (q!= NULL)
    {
        free(q);
    }
}

int Queue::InSQType(SQType *q, DATA data)
{
    if (q->tail == QUEUELEN)
    {
        std::cout<< "队列已满!操作失败!\n";
        return 0;
    }
    else
    {
        q->data[q->tail++] = data;
        return 1;
    }
}

DATA *Queue::OutSQType(SQType *q)
{
    if (q->head == q->tail)
    {
        std::cout<< "\n队列已空!操作失败!\n";
        exit(0);
    }
    else
    {
        return &(q->data[q->head++]);
    }
}

DATA *Queue::PeekSQType(SQType *q)
{
    if (SQTypeIsEmpty(q))
    {
        std::cout<< "\n空队列!\n";
        return NULL;
    }
    else
    {
        return &(q->data[q->head]);
    }
}

int Queue::SQLTypeLen(SQType *q)
{
    int temp;
    temp = q->tail - q->head;
    return temp;
}

Queue * Queue::create()
{
    Queue * pRet = new Queue();
    if (pRet && pRet->init())
    {
        //pRet->autorelease();
    }
    else
    {
        delete pRet;
    }
	return pRet;
}


bool Queue::init()
{
    return true;
}

main.cpp

#include 
  
   
#include "Queue.h"

using namespace std;

int main(int argc, const char * argv[])
{
    SQType *stack;
    DATA data;
    DATA *data1;
    
    Queue *myQueue = Queue::create();
    stack = myQueue->SQTypeInit();
    std::cout << "队列操作演示\n";
    std::cout << "输入(姓名 年龄)进行入队列操作:";
    fflush(stdin);  //清空输入缓冲区
    do
    {
        scanf("%s%d",data.name,&data.age);
        
        if (strcmp(data.name, "0") == 0)
        {
            break;
        }
        else
        {
            myQueue->InSQType(stack, data);
        }
        
    } while (1);
    
    do
    {
        std::cout << "出队列操作:按任意键进行出栈操作:\n";
        getchar();
        data1 = myQueue->OutSQType(stack);
        printf("出队列的数据是(%s,%d)\n",data1->name,data1->age);
    } while (1);
    
    myQueue->SQTypeFree(stack);
    delete myQueue;
    // std::cout << "Hello, World!\n";
    return 0;
}

演示效果图:

参考书籍:《C/C++常用算法手册》《数据结构-清华大学严蔚敏》

c/c++常用算法(4) -- 数据结构(队列)

一、概念

二、队列的抽象数据类型定义

三、代码实现: