栈: 后进先出(LIFO)

队列: 先进先出(FIFO)

  • 栈和队列的一些应用
    1. 信号量: 同步多个进程访问共享资源
    2. 事件处理
    3. X Window 系统, 使用队列来存储事件
    4. 生产者-消费者问题, 生产者向队列中写入数据, 消费从队列中读出数据
    5. C 函数的调用, 函数的调用会将一些信息压入程序栈, 程序结束时将信息出栈

栈最常用的是使用链表来实现, 以下是栈的抽象数据类型头文件

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/* stack.h */
#ifndef STACK_H
#define STACK_H

/* 元素结点 */
typedef struct StackElmt_ {
    void *data;
    struct StackElmt_ *next;
}StackElmt;

/* 栈结构 */
typedef struct Stack_ {
    /* 栈大小 */
    int size;
    /* 指向栈顶结点 */
    StackElmt *top;
    void (*destroy)(void *data);
    void (*match)(const void *key1, const void *key2);
}Stack;

/* 初始化 */
void stack_init(Stack *stack, void (*destroy)(void *data));
/* 销毁 */
void stack_destroy(Stack *stack);
/* 插入结点 */
int stack_push(Stack *stack, const void *data);
/* 弹出结点 */
int stack_pop(Stack *stack, void **data);
/* 空栈返回 NULL, 非空栈返回头指针指向数据 */
#define stack_peek(stack) ((stack)->top == NULL ? NULL : (stack)->top->data)
/* 返回栈大小 */
#define stack_size(stack) ((stack)->size)

#endif

栈的实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/* stack.c */
#include <stdlib.h>
#include "stack.h"

/* 初始化 */
void stack_init(Stack *stack, void (*destroy)(void *data))
{
    stack.size = 0;
    stack.destroy = destroy;
    stack.top = NULL;
}

/* 销毁 */
void stack_destroy(Stack *stack)
{
    void *data;

    while (stack->size > 0) {
        if (stack_pop(stack, (void **)&data) == 0 && stack->destroy != NULL) {
            stack->destroy(data);
        }
    }
    memset(stack, 0, sizeof(Stack));
}

/* 弹出结点 */
int stack_pop(Stack *stack, void **data)
{
    StackElmt *element;

    if (stack->size == 0) {
        return -1;
    }
    element = stack->top;
    stack->top = element->next;
    free(element);
    stack->size--;
    return 0;
}

/* 压入结点 */
int stack_push(Stack *stack, const void *data)
{
    StackElmt *element;
    if ((element = (StackElmt *)malloc(sizeof(StackElmt))) == NULL) {
        return -1;
    }
    element->data = data;
    element->next = stack->top;
    stack->top = element;
    stack->size++;
    return 0;
}

队列其实就是一个链表结构, 但只提供了先进先出的接口 队列头文件定义

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/* queue.h */
#ifndef QUEUE_H
#define QUEUE_H

/* 元素结点 */
typedef struct QueueElmt_ {
    void *data;
    struct QueueElmt_ *next;
}QueueElmt;

/* 队列结构 */
typedef struct Queue_ {
    /* 队列大小 */
    int size;
    /* 指向队列头结点 */
    QueueElmt *head;
    /* 队列尾结点 */
    QueueElmt *tail;
    void (*destroy)(void *data);
    void (*match)(const void *key1, const void *key2);
}Queue;

/* 初始化 */
void queue_init(Queue *queue, void (*destroy)(void *data));
/* 销毁 */
void queue_destroy(Queue *queue);
/* 插入结点 */
int queue_enqueue(Queue *queue, const void *data);
/* 弹出结点 */
int queue_dequeue(Queue *queue, void **data);
/* 空栈返回 NULL, 非空栈返回头指针指向数据 */
#define queue_peek(queue) ((queue)->head == NULL ? NULL : (queue)->top->data)
/* 返回栈大小 */
#define queue_size(queue) ((queue)->size)


#endif

队列抽象数据类型的实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/* queue.h */
#include <stdlib.h>
#include <string.h>
#include "queue.h"

/* 初始化 */
void queue_init(Stack *queue, void (*destroy)(void *data))
{
    queue.size = 0;
    queue.destroy = destroy;
    queue.head = NULL;
    queue.tail = NULL;
}

/* 销毁 */
void queue_destroy(Stack *queue)
{
    void *data;

    while (queue->size > 0) {
        if (queue_dequeue(queue, (void **)&data) == 0 && queue->destroy != NULL) {
            queue->destroy(data);
        }
    }
    memset(queue, 0, sizeof(Queue));
}

/* 入队 */
int queue_enqueue(Queue *queue, const void *data)
{
    QueueElmt *element;
    if ((element = (QueueElmt *)malloc(sizeof(QueueElmt))) == NULL) {
        return -1;
    }
    element->data = (void *)data;
    if (queue->size == 0) {
        /* 空队列 */
        queue->head = element;
    } else {
        queue->tail->next = element;
    }
    queue->tail = element;
    element->next = NULL;
    queue->size++;
    return 0;

}

/* 出队 */
int queue_dequeue(Queue *queue, void **data)
{
    QueueElmt *element;
    if (queue->size == 0) {
        return -1;
    }
    element = queue->head;
    data = (void **)&element->data;
    if (element->next == NULL) {
        /* 队列中只有一个结点 */
        queue->head = NULL;
        queue->tail = NULL;
    } else {
        queue->head = element->next;
    }
    free(element);
    queue->size--;
    return 0;
}