005-数据结构和算法-链式队列

2020-04-15  本文已影响0人  沉默Coder

上一章我们讨论了队列的顺序存储的实现,这一章我们换一种方式来实现队列

链式队列实现

我们再次强调,队列只是一种逻辑结构,是一种“先进先出”的线性表,所以和线性表一样,我们可以采用:
-顺序存储
-链式存储
的方式来实现队列。
这一章我们重点讲解如何使用链式存储的方式实现一个队列,如果对顺序存储方式实现不清楚的可以查看一下这篇文章 队列的顺序实现;

一些提前定义的变量和结构体:

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;
typedef int Element; /* Element类型根据实际情况而定,这里假设为int */

//定义节点
typedef struct SqNode
{
    Element data;
    struct SqNode * next;
} SqNode;
//定义队列,实际我们只需要使用定义队头和队尾指针
typedef struct
{
    SqNode *front, *rear;
}SqQueue;

创建队列,我们这里使用一个头节点来标记队列的队头,头节点不存储数据,只是为了方面后续的操作

/// 初始化队列,创建队列中链表的头节点
Status InitQueue(SqQueue * Q)
{
    Q->front = Q->rear = (SqNode *)malloc(sizeof(SqNode));
    
    if (Q->front == NULL) {
        return ERROR;
    }
    
    Q->front->next = NULL;
    
    return OK;
}
///销毁队列,头节点也需要销毁
Status destroyQueue(SqQueue * Q)
{
    //已经在销毁队列了,所以认为Q->rear已经失去了存在的意义,所以这里用Q->rear来标记Q->front的下一个节点
    while (Q->front) {
        
        Q->rear = Q->front->next;
        Q->front->next = NULL;
        free(Q->front);
        Q->front = Q->rear;
    }
    
    return OK;
}
/// 清空队列,保留头节点
Status clearQueue(SqQueue *Q)
{
    if(Q->front == Q->rear) return OK;
    
    SqNode *p,*k;
    
    p = Q->front->next;
    Q->rear = Q->front;
    Q->front->next = NULL;
    
    while (p) {
        
        k = p->next;
        free(p);
        p = k;
    }
    
    return OK;
}
/// 队列是否为空,如果队头和队尾指针指向了同一个元素,则表示该队列为空队列
Status isQueueEmpty(SqQueue Q)
{
    return Q.front == Q.rear;
}
///队列的长度
Status queueLength(SqQueue Q)
{
    int i = 0;
    SqNode *p = Q.front->next;
    while (p) {
        i++;
        p = p->next;
    }
    
    return i;
}
/// 元素入队,
Status inQueue(SqQueue *Q,Element e)
{
    if(Q->front == NULL) return ERROR;
    
    SqNode * node = (SqNode *)malloc(sizeof(SqNode));
    if(node == NULL) return ERROR;
    node->data = e;
    node->next = NULL;
    
    //将新元素添加到队尾
    Q->rear->next = node;
    //将队尾指针指向最后一个位置
    Q->rear = node;
    
    return OK;
}
/// 出队
Status outQueue(SqQueue *Q, Element *e)
{
    //判断队列是否y为空
    if(Q->rear == Q->front) return ERROR;
    
    SqNode * s = Q->front->next;
    Q->front->next = s->next;
    *e = s->data;
    s->next = NULL;
    //判断弹出的元素是不是在队尾,如果是,则需要将队尾指针指向对头,否则释放后,Q->rear将是野指针
    if(Q->rear == s) Q->rear = Q->front;
    free(s);
    
    return OK;
}
/// 获取对头元素
Status getHead(SqQueue Q,Element *e)
{
    //判断队列是否为空
    if(Q.rear == Q.front) return ERROR;
    
    *e = Q.front->next->data;
    return OK;
}
///打印队列元素
void printQueue(SqQueue Q)
{
    if(Q.front == Q.rear) return;
    
    SqNode * p = Q.front->next;
    printf("队列元素:");
    while (p) {
        
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

测试

int main(int argc, const char * argv[]) {
    // insert code here...
    
    Status iStatus;
    Element d;
    SqQueue q;
    
    //1.初始化队列q
    iStatus = InitQueue(&q);
    
    //2. 判断是否创建成
    if (iStatus) {
        printf("成功地构造了一个空队列\n");
    }
    
    //3.判断队列是否为空
    printf("是否为空队列?%d (1:是 0:否)\n",isQueueEmpty(q));
    
    //4.获取队列的长度
    printf("队列的长度为%d\n",queueLength(q));
    
    //5.插入元素到队列中
    inQueue(&q, -3);
    inQueue(&q, 6);
    inQueue(&q, 12);
    
    printf("队列的长度为%d\n",queueLength(q));
    printf("是否为空队列?%d (1:是 0:否)\n",isQueueEmpty(q));
    
    //6.遍历队列
    printQueue(q);

    //7.获取队列头元素
    iStatus = getHead(q, &d);
    if (iStatus == OK) {
        printf("队头元素是:%d\n",d);
    }
    
    //8.删除队头元素
    iStatus =outQueue(&q, &d);
    if (iStatus == OK) {
        printf("删除了的队头元素为:%d\n",d);
    }
    
    //9.获取队头元素
    iStatus = getHead(q, &d);
    if (iStatus == OK) {
        printf("新的队头元素为:%d\n",d);
    }
    
    //10.清空队列
    clearQueue(&q);
    
    //11.销毁队列
    destroyQueue(&q);
    
    
    return 0;
}

结果输出:


测试结果
上一篇下一篇

猜你喜欢

热点阅读