C语言数据结构之栈和队列的实现及应用

什么是栈和队列？

栈是一种具有后进先出（LIFO）特性的线性数据结构，可以理解为一个只能在一端进行插入和删除操作的数据结构。通常称插入元素的一端为栈顶，删除元素的一端为栈底。

队列是一种具有先进先出（FIFO）特性的线性数据结构，可以理解为一个只能在两端进行插入和删除操作的数据结构。一端进行插入操作，称之为队尾，一端进行删除操作，称之为队首。

栈的实现及应用

栈的实现

在C语言中实现栈用数组和链表两种方式。下面我们讨论数组实现方式。

首先需要定义一个数组和一个指针，指针指向栈顶元素。实现push和pop操作时，修改指针位置并操作数组内容即可。

#define MAX_SIZE 1000

typedef struct {
    int a[MAX_SIZE];
    int top;
} Stack;

void push(Stack *s, int x) {
    if(s->top < MAX_SIZE) {
        s->a[s->top++] = x;
    } else {
        printf("Stack overflow!\n");
    }
}

int pop(Stack *s) {
    if(s->top > 0) {
        return s->a[--s->top];
    } else {
        printf("Stack underflow!\n");
        return -1;
    }
}

栈的应用

常见的栈的应用场景有表达式求值、括号匹配、迷宫问题等，下面我们简单介绍两个示例。

示例1：表达式求值

算术表达式通常是用中缀表示，即操作数在中间，操作符在两侧。为了求值表达式，我们通常将中缀表达式转成后缀表达式，然后用栈求值。下面是示例代码：

int getPrior(char op) {
    if(op == '+' || op == '-') {
        return 1;
    }
    if(op == '*' || op == '/') {
        return 2;
    }
    if(op == '(' || op == ')') {
        return 0;
    }
    return -1;
}

int isOp(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')';
}

void infix2postfix(char *infix, char *postfix) {
    Stack s;
    s.top = 0;
    int i, j;
    for(i = 0, j = 0; infix[i]; i++) {
        if(!isOp(infix[i])) {
            postfix[j++] = infix[i];
        } else if(infix[i] == ')') {
            while(s.top && s.a[s.top-1] != '(') {
                postfix[j++] = s.a[--s.top];
            }
            if(s.top) {
                s.top--;
            }
        } else {
            while(s.top && getPrior(s.a[s.top-1]) >= getPrior(infix[i])) {
                postfix[j++] = s.a[--s.top];
            }
            s.a[s.top++] = infix[i];
        }
    }
    while(s.top) {
        postfix[j++] = s.a[--s.top];
    }
    postfix[j] = '\0';
}

int postfixEval(char *postfix) {
    Stack s;
    s.top = 0;
    int i, a, b, c;
    for(i = 0; postfix[i]; i++) {
        if(!isOp(postfix[i])) {
            push(&s, postfix[i] - '0');
        } else {
            a = pop(&s);
            b = pop(&s);
            switch(postfix[i]) {
                case '+':
                    c = a + b;
                    break;
                case '-':
                    c = b - a;
                    break;
                case '*':
                    c = a * b;
                    break;
                case '/':
                    c = b / a;
                    break;
            }
            push(&s, c);
        }
    }
    return pop(&s);
}

示例2：括号匹配

括号匹配问题也可以使用栈来解决。我们遍历字符串，并用栈记录左括号，遇到右括号时出栈一个左括号并匹配，如果不匹配直接返回。

int isMatch(char a, char b) {
    return (a == '(' && b == ')') || (a == '[' && b == ']') || (a == '{' && b == '}');
}

int isBalanced(char *s) {
    Stack stk;
    stk.top = 0;
    int i;
    for(i = 0; s[i]; i++) {
        if(s[i] == '(' || s[i] == '[' || s[i] == '{') {
            push(&stk, s[i]);
        } else if(s[i] == ')' || s[i] == ']' || s[i] == '}') {
            if(!stk.top || !isMatch(stk.a[stk.top-1], s[i])) {
                return 0;
            }
            stk.top--;
        }
    }
    return stk.top == 0;
}

队列的实现及应用

队列的实现

在C语言中实现队列用数组和链表两种方式。下面我们讨论数组实现方式。

与栈相似，需要定义一个数组和两个指针，一个指向队头元素，一个指向队尾元素。实现enqueue和dequeue操作时，修改指针位置并操作数组内容即可。

#define MAX_SIZE 1000

typedef struct {
    int a[MAX_SIZE];
    int front, rear;
} Queue;

void enqueue(Queue *q, int x) {
    if(q->rear < MAX_SIZE) {
        q->a[q->rear++] = x;
    } else {
        printf("Queue overflow!\n");
    }
}

int dequeue(Queue *q) {
    if(q->front < q->rear) {
        return q->a[q->front++];
    } else {
        printf("Queue underflow!\n");
        return -1;
    }
}

队列的应用

常见的队列的应用场景有FIFO算法、消息队列、排队系统等，下面我们简单介绍两个示例。

示例1：FIFO算法

FIFO（First In First Out）算法是一种页面置换算法，也称先进先出算法。它选择最早调入内存的页面进行置换。

#define MEM_SIZE 4

int pageFaults(int *references, int n) {
    Queue q;
    q.front = q.rear = 0;
    int mem[MEM_SIZE] = {0};
    int i, j, faults = 0;
    for(i = 0; i < n; i++) {
        int found = 0;
        for(j = 0; j < MEM_SIZE; j++) {
            if(references[i] == mem[j]) {
                found = 1;
                break;
            }
        }
        if(found) {
            // already in memory
        } else if(q.rear < MEM_SIZE) {
            mem[q.rear++] = references[i];
            enqueue(&q, references[i]);
            faults++;
        } else {
            int top = dequeue(&q);
            for(j = 0; j < MEM_SIZE; j++) {
                if(mem[j] == top) {
                    mem[j] = references[i];
                    break;
                }
            }
            enqueue(&q, references[i]);
            faults++;
        }
    }
    return faults;
}

示例2：消息队列

消息队列是一种异步通信机制，常用于进程间通信。一个进程将消息发送到队列，另一个进程从队列中读取消息。

#define MAX_SIZE 1000

typedef struct {
    int queue[MAX_SIZE];
    int front, rear;
    pthread_mutex_t mutex;
    pthread_cond_t notEmpty, notFull;
} MsgQueue;

void initMsgQueue(MsgQueue *q) {
    q->front = q->rear = 0;
    pthread_mutex_init(&q->mutex, NULL);
    pthread_cond_init(&q->notEmpty, NULL);
    pthread_cond_init(&q->notFull, NULL);
}

void sendMsg(MsgQueue *q, int msg) {
    pthread_mutex_lock(&q->mutex);
    while(q->rear - q->front >= MAX_SIZE) {
        pthread_cond_wait(&q->notFull, &q->mutex);
    }
    q->queue[q->rear++ % MAX_SIZE] = msg;
    pthread_mutex_unlock(&q->mutex);
    pthread_cond_signal(&q->notEmpty);
}

int recvMsg(MsgQueue *q) {
    int msg;
    pthread_mutex_lock(&q->mutex);
    while(q->rear <= q->front) {
        pthread_cond_wait(&q->notEmpty, &q->mutex);
    }
    msg = q->queue[q->front++ % MAX_SIZE];
    pthread_mutex_unlock(&q->mutex);
    pthread_cond_signal(&q->notFull);
    return msg;
}