数据结构C-队列（五）

//
//  main.c
//  Queue
//
//  Created by 季晓东 on 2019/1/18.
//  Copyright © 2019 季晓东. All rights reserved.
//

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

//定bool类型的值true|false
#define true 1
#define false 0

#define EXIT -1
#define ZERO 0

//自定义bool数据类型
typedef int bool;

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct Queue {
    Node *node;
    Node *front;
    Node *tail;
    int size;
} Queue;


//----------------------------------------------函数声明----------------------------------------------------------------
//自定义错误提示
void error(char* msg);

//自定义警告提示
void warning(char* msg);

//初始化
void init(Queue *queue);

//获得栈的长度
int getSize(Queue *queue);

//判断queue是否为空
bool isEmpty(Queue *queue);

//入栈
void enqueue(Queue *queue, int e);

//出栈
int dequeue(Queue *queue);

//查看栈顶元素
int getFront(Queue *queue);

//是否包含某元素
bool contains(Queue *queue, int e);

//显示信息
void show(Queue *queue);

//----------------------------------------------函数实现----------------------------------------------------------------

void error(char* msg) {
    printf("\n---------------------------------------------------------------------------\n");
    printf("ERROR: %s", msg);
    printf("\n---------------------------------------------------------------------------\n\n");
}

void warning(char* msg) {
    printf("\n---------------------------------------------------------------------------\n");
    printf("WARNING: %s", msg);
    printf("\n---------------------------------------------------------------------------\n\n");
}

void init(Queue *queue) {
    Node *dummyHead = (Node *)malloc(sizeof(Node));
    queue->tail = (Node *)malloc(sizeof(Node));
    queue->front = (Node *)malloc(sizeof(Node));
    if (queue == NULL && queue->tail != NULL && queue->front != NULL) {
        error("Queue memory allocation failed.");
        exit(EXIT);
    }
    
    dummyHead->next= NULL;
    queue->front = dummyHead;
    queue->tail = dummyHead;
    queue->node = dummyHead;
}

int getSize(Queue *queue) {
    return queue->size;
}

bool isEmpty(Queue *queue) {
    return queue->size == ZERO;
}

void enqueue(Queue *queue, int e) {
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = e;
    node->next = NULL;
    
    //    时间复杂度O(1)
    queue->tail->next = node;
    queue->tail = node;
    if (queue->size == 0) {
        queue->front = node;
    }
    queue->size++;
}

int dequeue(Queue *queue) {
    //  时间复杂度O(1)
    Node *delNode = queue->front;
    queue->node->next = delNode->next;
    queue->size--;
    queue->front = delNode->next;
    return delNode->data;
}

int getFront(Queue *queue) {
    return queue->front->data;
}

bool contains(Queue *queue, int e) {
    Node *cur = queue->node->next;
    while (cur != NULL) {
        if (e == cur->data) {
            return true;
        }
        cur = cur->next;
    }
    return false;
}

void show(Queue *queue) {
    printf("Queue: size=%d, ",queue->size);
    Node *node = queue->node->next;
    while (node != NULL) {
        printf("%d->",node->data);
        node = node->next;
    }
    printf("null\n");
}

//----------------------------------------------main函数----------------------------------------------------------------

int main(int argc, const char * argv[]) {
    
    Queue queue;
    
    init(&queue);
    
    enqueue(&queue, 1);
    show(&queue);
    
    enqueue(&queue, 2);
    show(&queue);
    
    dequeue(&queue);
    show(&queue);
    
    enqueue(&queue, 6);
    show(&queue);
    
    enqueue(&queue, 60);
    show(&queue);
    
    
    printf("getFront = %d\n",getFront(&queue));
    
    dequeue(&queue);
    show(&queue);
    
    printf("getFront = %d\n",getFront(&queue));
    
    dequeue(&queue);
    show(&queue);
    
    return 0;
}