纸上谈兵: 队列 (queue)

  • 时间:
  • 浏览:0
  • 来源:极速快3_快3怎么注册_极速快3怎么注册

作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢!

队列(queue)是有八个 多多简单而常见的数据型态。队列也是有序的元素集合。队列最大的型态是First In, First Out (FIFO,先进先出),即先进入队列的元素,先被取出。你什儿 点与栈(stack)形成有趣的对比。队列在生活中很常见,排队买票、排队等车…… 先到的人先得到服务并拖累队列,然后 的人加入到队列的最后。队列是比较公平的分配有限资源的土法子 ,都能能让队列的人以相似于的等待获得服务。

队列支持有八个 多多操作,队首的元素拖累队列(dequeue),和新元素加入队尾(enqueue)

队列

队列在计算机中应用很广泛。有八个 多多经典的应用是消息队列(参考Linux任务管理器池池间通信),实际上就是 利用队列来分配有限的任务管理器池池。还有FIFO文件(哦,我就看了,你什儿 文件叫做FIFO,肯定是和队列有关),用以实现管道传输。再比如,大家 将多个打印任务发送给打印机,打印机也是使用队列来安排任务的顺序。

队列的C实现 (基于表)

和栈相似于,队列也都能能有多种实现土法子 ,这里是基于单链表的实现。

与表(list)中的实现土法子 略有不同的是,这里的head node有有八个 多多指针,有八个 多多(next)指向下有八个 多多元素,有八个 多多(end)指向队列的最后有八个 多多元素。从前做的目的是方便大家 找到队尾,以方便的进行enqueue操作。大家 依然都能能使用然后 定义的表,在都能能找到队尾的然后 遍历搜索到最后有八个 多多元素。

用于队列的表

下面是代码:

/* By Vamei */
/* use single-linked list to implement queue */
#include <stdio.h>
#include <stdlib.h>

typedef struct node *position;
typedef int ElementTP;

// point to the head node of the list
typedef struct HeadNode *QUEUE;
 
struct node {
    ElementTP element;
    position next;
};

/*
 * CAUTIOUS: "HeadNode" is different from "node", 
 * it's another struct
 * end: points to the last value in the queue
 */
struct HeadNode {
    ElementTP element;
    position next;
    position end;
};


/*
 * Operations
 */
QUEUE init_queue(void);
void delete_queue(QUEUE);
void enqueue(QUEUE, ElementTP);
ElementTP dequeue(QUEUE);
int is_null(QUEUE);

/*
 * Test
 */
void main(void)
{
    ElementTP a;
    int i;
    QUEUE qu;
    qu = init_queue();

    enqueue(qu, 1);
    enqueue(qu, 2);
    enqueue(qu, 8);
    printf("Queue is null? %d\n", is_null(qu));
    for (i=0; i<3; i++) {
        a = dequeue(qu);
        printf("dequeue: %d\n", a);
    }

    printf("Queue is null? %d\n", is_null(qu));    
    delete_queue(qu);
}

/*
 * initiate the queue
 * malloc the head node.
 * Head node doesn't store valid data
 * head->next is the first node in the queue.
 */
QUEUE init_queue(void)
{
    QUEUE hnp;
    hnp = (QUEUE) malloc(sizeof(struct HeadNode));
    hnp->next = NULL;  // qu->next is the first node
    hnp->end  = NULL;
    return hnp;
}

/*
 * dequeue all elements 
 * and then delete head node
 */
void delete_queue(QUEUE qu)
{
    while(!is_null(qu)) {
        dequeue(qu);
    }
    free(qu);
}

/*
 * enqueue a value to the end of the queue 
 */
void enqueue(QUEUE qu, ElementTP value) 
{
    position np, oldEnd;
    oldEnd = qu->end;    

    np = (position) malloc(sizeof(struct node));
    np->element  = value;
    np->next     = NULL;

    /* if queue is empyt, then oldEnd is NULL */
    if (oldEnd) {
        oldEnd->next = np;
    }
    else {
        qu->next     = np;
    }

    qu->end = np; 
}

/* 
 * dequeue the first value
 */
ElementTP dequeue(QUEUE qu)
{
    ElementTP element;
    position first, newFirst;
    if (is_null(qu)) {
        printf("dequeue() on an empty queue");
        exit(1);
    } 
    else {
        first        = qu->next;
        element      = first->element;     
        newFirst     = first->next;
        qu->next     = newFirst;
        free(first);
        return element;
    } 
}

/*
 * check: queue is empty?
 */
int is_null(QUEUE qu)
{
    return (qu->next == NULL);
}

运行结果如下:

Queue is null? 0

dequeue: 1dequeue: 2dequeue: 8Queue is null? 1

总结

队列,FIFO

enqueue, dequeue

欢迎继续阅读“纸上谈兵: 算法与数据型态”系列。