队列实现 (双向循环链表 C++)

队列是很简单的,但是用数组实现可能更好点。。(其实我觉得数组在多个队列的时候更难)


然后我是第一次写双向循环链表。指向太乱了。

我这里是按照自己的想法,建立了一个头节点,一个尾节点,然后按照队列顺序正向插入到两个节点之间。输出和弹出队列的时候从后面操作。


下面上代码:

//
//  main.cpp
//  queue
//
//  Created by Alps on 14-7-28.
//  Copyright (c) 2014年 chen. All rights reserved.
//

#include <iostream>
#define ElementType int

using namespace std;

struct Node;
typedef Node* PtrToNode;
typedef PtrToNode Queue;

struct Node{
    ElementType X;
    PtrToNode Pre;
    PtrToNode Next;
};

Queue createQueue(void){
    Queue Q;
    Queue Q2;
    Q2 = (Queue)malloc(sizeof(Queue));
    Q = (Queue)malloc(sizeof(Queue));
    Q->X = 0;
    Q->Next = Q2;
    Q->Pre = Q2;
    Q2->Next = Q;
    Q2->Pre = Q;
    return Q;
}

int isEmpty(Queue Q){
    return Q->Next->Next == Q;
}

void intoQueue(Queue Q, ElementType element){
    Queue tmp;
    Queue tmp1;
    tmp1 = (Queue)malloc(sizeof(Queue));
//    Queue switchTmp;
    tmp = (Queue)malloc(sizeof(Queue));
    tmp->X = element;
    tmp->Next = Q->Next;
    Q->Next->Pre = tmp;
    Q->Next = tmp;
    tmp->Pre = Q;
}

void outQueue(Queue Q){
    Queue tmp;
    tmp = Q->Pre->Pre;
    Q->Pre->Pre = tmp->Pre;
    tmp->Pre->Next = Q->Pre;
    free(tmp);
}

ElementType headQueue(Queue Q){
    if (Q == NULL) {
        printf("please create queue first!\n");
        return 0;
    }
    if (!isEmpty(Q)) {
        return Q->Pre->Pre->X;
    }else{
        printf("The queue is empty!\n");
        return 0;
    }
}

int makeEmpty(Queue Q){
    if (Q == NULL) {
        printf("please create queue first!\n");
        return -1;
    }
    while (!isEmpty(Q)) {
        outQueue(Q);
    }
    return 0;
}

void Print(Queue Q){
    if (!isEmpty(Q)) {
        Queue tmp = Q->Pre->Pre;
        while (tmp != Q) {
            printf("%d ",tmp->X);
            tmp = tmp->Pre;
        }
        printf("\n");
    }
}

int main(int argc, const char * argv[])
{
    Queue Q = createQueue();
    if (isEmpty(Q)) {
        printf("The queue is empty !\n");
    }else{
        printf("The queue is not empty!\n");
    }
    intoQueue(Q, 2);
    intoQueue(Q, 4);
    intoQueue(Q, 6);
    Print(Q);
    outQueue(Q);
    Print(Q);
    makeEmpty(Q);
    Print(Q);
//    printf("%d\n",headQueue(Q));
    return 0;
}

这个代码比较乱 = = ,多包涵了,我以后想想简单点的方法实现。其实单链表也可以,但是那样操作就不是O(1)了,所以才用双链表。

队列实现 (双向循环链表 C++),布布扣,bubuko.com

队列实现 (双向循环链表 C++)

上一篇:进程和线程的一个简单形象的解释


下一篇:【美妙的Python之五】标准变量类型-列表,元组与元字典