数据结构-第三章-循环顺序队-增设标记法实现各种基本功能

数据结构-第三章-循环顺序队-增设标记法实现各种基本功能

**文件名后缀应为.cpp
文件名后缀应为.cpp
文件名后缀应为.cpp**

在循环队列的基础上增设标记tag成员变量
入队成功tag=1
出队成功tag=0

**该方法是区分队空队满以下三种方法中的第三种 （详见王道书）
方法一：牺牲一个单元来区分队空队满。（易，但浪费空间）
方法二：数据结构中增设表示元素个数的数据成员。（易）
方法二：数据结构中增设表示元素个数的数据成员。（与二一样，但这种就更巧妙一点，这种思想更重要，对其他算法有非常大的帮助）**

详细注释以后再更新
-------------------------------------------------------------------------------------------------------------------------

#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MaxSize 20
#define ElemType int

typedef struct {
    ElemType data[MaxSize];
    int front, rear, tag;
} SqQueue;

void InitQueue( SqQueue &Q );                //定义 初始化顺序队 函数
bool QueueEmpty( SqQueue Q );                //定义 判断顺序队空 函数
bool QueueFull( SqQueue Q );                //定义 判断顺序队满 函数
int QueueLength( SqQueue Q );                //定义 返回队的长度 函数
bool EnQueue( SqQueue &Q, ElemType x );        //定义 入队 函数
bool DeQueue( SqQueue &Q, ElemType &x );    //定义 出队 函数
bool GetHead( SqQueue Q, ElemType &x );        //定义 获取队头元素 函数
bool ClearQueue( SqQueue &Q );                //定义 清空顺序队 函数

void PrintQueue( SqQueue Q );
int main() {

    srand( ( unsigned )time( NULL ) );

    SqQueue Q;//定义一个顺序队
    InitQueue( Q );//初始化顺序队
    printf( "\n入队前：\n" );
    printf( "空结果：%d\n", QueueEmpty( Q ) );
    printf( "满结果：%d\n", QueueFull( Q ) );

//    测试入队函数
    for( int i = 0; i < 20; i++ ) {
        EnQueue( Q, i );
    }
    PrintQueue( Q );

    printf( "\n入队后及出队前：\n" );
    printf( "空结果：%d\n", QueueEmpty( Q ) );
    printf( "满结果：%d\n", QueueFull( Q ) );


    //测试 弹出队函数
    printf( "出队元素依次为：\n" );
    for( int i = 0; i < 19; i++ ) {
        int x;
        DeQueue( Q, x );
        printf( "%d ", x );
    }
    printf( "\n" );
    PrintQueue( Q );

    printf( "\n出队后：\n" );
    printf( "空结果：%d\n", QueueEmpty( Q ) );
    printf( "满结果：%d\n", QueueFull( Q ) );

    //测试读取队头元素函数
    int x;
    if( GetHead( Q, x ) ) {
        printf( "Q.data[Q.front]= %d \n", x );
    } else {
        printf( "队空，读取失败！\n" );
    }

    //测试清空队函数
    ClearQueue( Q );
    PrintQueue( Q );

    return 0;
}

//实现 初始化顺序队 函数
void InitQueue( SqQueue &Q ) {
    Q.front = Q.rear = Q.tag = 0;
}

//实现 判断顺序队空 函数
bool QueueEmpty( SqQueue Q ) {
    if( Q.front == Q.rear && Q.tag == 0 )
        return true;
    else
        return false;
}

//实现 判断顺序队满 函数
bool QueueFull( SqQueue Q ) {
    if( Q.front == Q.rear && Q.tag == 1 )
        return true;
    else
        return false;
}

//实现 返回队的长度 函数
int QueueLength( SqQueue Q ) {
    int len = ( Q.rear - Q.front + MaxSize  ) % MaxSize;
    if( len == 0 && Q.tag == 0 ) {
        return 0;
    }
    if( len == 0 && Q.tag == 1 ) {
        return MaxSize;
    }
    return len;
}

//实现 入队 函数
bool EnQueue( SqQueue &Q, ElemType x ) {
    if( QueueFull( Q ) )    //判断队是否满，若满则入队失败，返回false
        return false;

    Q.data[Q.rear] = x;
    Q.rear = ( Q.rear + 1 ) % MaxSize;
    Q.tag = 1;

    return true;
}

//实现 出队 函数
bool DeQueue( SqQueue &Q, ElemType &x ) {
    if( QueueEmpty( Q ) )
        return false;

    x = Q.data[Q.front];
    Q.front = ( Q.front + 1 ) % MaxSize;
    Q.tag = 0;

    return true;
}

//实现 获取队头元素 函数
bool GetHead( SqQueue Q, ElemType &x ) {
    if( QueueEmpty( Q ) )
        return false;
    x = Q.data[Q.front];

    return true;
}

//实现 清空顺序队 函数
bool ClearQueue( SqQueue &Q ) {
    Q.front = Q.rear = Q.tag = 0;
    return true;
}

void PrintQueue( SqQueue Q ) {
    if( QueueEmpty( Q ) ) {
        printf( "\n队空\n" );
        return;
    }

    printf( "当前队列元素为：\n" );
    int i = Q.front;
    while( 1 ) {
        printf( "%d ", Q.data[i] );
        i = ( i + 1 ) % MaxSize;
        if( i == Q.rear )break;
    }

    printf( "\n共%d个元素\n", QueueLength( Q ) );
}