C语言数据结构进阶之栈和队列的实现

什么是栈？

栈是一种数据结构，具有后进先出（LIFO）的特点。这意味着最后插入的数据最先被取出。在栈中，插入和删除数据只发生在一端，称为栈顶（top），另一端称为栈底（bottom）。下面介绍如何使用 C 语言实现栈的基本操作。

栈的基本操作

• push：将元素压入栈顶。
• pop：将元素从栈顶弹出。
• isEmpty：检查栈是否为空。
• isFull：检查栈是否已满，通常用于数组实现的栈。

栈的实现方式

1. 数组实现

使用数组可以较简单地实现一个栈。定义一个数组存储栈元素，再定义一个栈顶指针，可以记录栈顶元素的位置。当元素入栈时，将它添加到数组末尾，并将栈顶指针加一；当元素出栈时，将栈顶指针减一，然后返回栈顶元素。

```c
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int top;
} Stack;

void push(Stack *s, int x) {
if (s->top >= MAX_SIZE) {
printf("ERROR: Stack is full\n");
return;
}
s->data[++s->top] = x;
}

int pop(Stack *s) {
if (s->top == -1) {
printf("ERROR: Stack is empty\n");
return -1;
}
return s->data[s->top--];
}

int isEmpty(Stack *s) {
return s->top == -1;
}
```

1. 链表实现

另一种实现栈的方式是使用链表。链表是一种递归的数据结构，其结点包含了当前元素的值和一个指向下一个结点的指针。在实现栈时，可以使用链表作为储存元素的容器。在链表的头部作为栈顶，并总是在链表顶部插入和删除元素。

```c
typedef struct Node {
int data;
struct Node* next;
} Node;

typedef struct {
Node *top;
} Stack;

void push(Stack s, int x) {
Node newNode = (Node *)malloc(sizeof(Node));
newNode->data = x;
newNode->next = s->top;
s->top = newNode;
}

int pop(Stack s) {
if (s->top == NULL) {
printf("ERROR: Stack is empty\n");
return -1;
}
Node popped = s->top;
int data = popped->data;
s->top = popped->next;
free(popped);
return data;
}

int isEmpty(Stack *s) {
return s->top == NULL;
}
```

栈的应用

• 判断括号匹配
• 二叉树的非递归遍历

什么是队列？

队列（queue）是一种数据结构，具有先进先出（FIFO）的特点。这意味着先插入的数据也会最先被取出。在队列中，插入操作只发生在队列尾部，称为队尾（rear）；删除操作只发生在队列头部，称为队头（front）。下面介绍如何使用 C 语言实现队列的基本操作。

队列的基本操作

• enqueue：将元素插入队尾。
• dequeue：将队头元素删除。
• isEmpty：检查队列是否为空。
• isFull：检查队列是否已满。

队列的实现方式

1. 数组实现

使用数组可以较简单地实现一个队列。定义一个数组存储队列元素，再定义两个指针 front 和 rear，分别指向队列头和队列尾。插入操作时，将元素添加到 rear 指向的位置，并将该指针加一；删除操作时，将 front 指针加一。

```c
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int front, rear;
} Queue;

void enqueue(Queue *q, int x) {
int nextRear = (q->rear + 1) % MAX_SIZE;
if (nextRear == q->front) {
printf("ERROR: Queue is full\n");
return;
}
q->data[q->rear] = x;
q->rear = nextRear;
}

int dequeue(Queue *q) {
if (q->front == q->rear) {
printf("ERROR: Queue is empty\n");
return -1;
}
int data = q->data[q->front];
q->front = (q->front + 1) % MAX_SIZE;
return data;
}

int isEmpty(Queue *q) {
return q->front == q->rear;
}
```

1. 链表实现

和栈一样，队列也可以用链表实现。定义一个链表结点，包含当前元素的值和一个指针，指向下一个结点。在队列中，使用一个指针 front 指向队头，并总是在链表尾部插入元素。

```c
typedef struct Node {
int data;
struct Node* next;
} Node;

typedef struct {
Node front, rear;
} Queue;

void enqueue(Queue q, int x) {
Node newNode = (Node *)malloc(sizeof(Node));
newNode->data = x;
newNode->next = NULL;
if (q->rear) {
q->rear->next = newNode;
}
q->rear = newNode;
if (q->front == NULL) {
q->front = newNode;
}
}

int dequeue(Queue q) {
if (q->front == NULL) {
printf("ERROR: Queue is empty\n");
return -1;
}
Node popped = q->front;
int data = popped->data;
q->front = popped->next;
if (q->front == NULL) {
q->rear = NULL;
}
free(popped);
return data;
}

int isEmpty(Queue *q) {
return q->front == NULL;
}
```

队列的应用

• 广度优先搜索算法（BFS）
• 模拟处理实体到达和离开事件

示例

使用栈实现计算器

思路：将中缀表达式转换成后缀表达式，再通过栈计算后缀表达式的值。

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define MAX_SIZE 100

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

void push(Stack *s, int x) {
  if (s->top >= MAX_SIZE) {
    printf("ERROR: Stack is full\n");
    return;
  }
  s->data[++s->top] = x;
}

int pop(Stack *s) {
  if (s->top == -1) {
    printf("ERROR: Stack is empty\n");
    return -1;
  }
  return s->data[s->top--];
}

int isEmpty(Stack *s) {
  return s->top == -1;
}

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

void infixToPostfix(char *infix, char *postfix) {
  Stack s;
  s.top = -1;
  int i, j;
  char ch, x;
  for (i = 0, j = 0; infix[i] != '\0'; i++) {
    ch = infix[i];
    if (isdigit(ch)) {
      postfix[j++] = ch;
    } else if (ch == '(') {
      push(&s, '(');
    } else if (ch == ')') {
      while ((x = pop(&s)) != '(') {
        postfix[j++] = x;
      }
    } else {
      while (!isEmpty(&s) && precedence(s.data[s.top]) >= precedence(ch)) {
        postfix[j++] = pop(&s);
      }
      push(&s, ch);
    }
  }
  while (!isEmpty(&s)) {
    postfix[j++] = pop(&s);
  }
  postfix[j] = '\0';
}

int evaluatePostfix(char *postfix) {
  Stack s;
  s.top = -1;
  int i, x, y, z;
  char ch;
  for (i = 0; postfix[i] != '\0'; i++) {
    ch = postfix[i];
    if (isdigit(ch)) {
      push(&s, ch - '0');
    } else {
      y = pop(&s);
      x = pop(&s);
      switch(ch) {
        case '+': z = x + y; break;
        case '-': z = x - y; break;
        case '*': z = x * y; break;
        case '/': z = x / y; break;
        default: break;
      }
      push(&s, z);
    }
  }
  return pop(&s);
}

int main() {
  char infix[MAX_SIZE], postfix[MAX_SIZE];
  printf("Enter an infix expression: ");
  fgets(infix, MAX_SIZE, stdin);
  infixToPostfix(infix, postfix);
  printf("Postfix expression: %s\n", postfix);
  printf("Result: %d\n", evaluatePostfix(postfix));
  return 0;
}

使用队列模拟实体到达和离开事件

思路：生成随机的实体到达事件和离开事件，将它们放到两个队列中，每次取两个队列的队头元素，并比较它们的时间戳，如果离开事件的时间戳早于到达事件，说明实体已经离开，弹出节点；否则实体进入处理，从到达队列中弹出节点并加入处理队列。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct {
  int id;
  int timestamp;
} Entity;

typedef struct Node {
  Entity data;
  struct Node* next;
} Node;

typedef struct {
  Node *front, *rear;
} Queue;

void enqueue(Queue *q, Entity x) {
  Node *newNode = (Node *)malloc(sizeof(Node));
  newNode->data = x;
  newNode->next = NULL;
  if (q->rear) {
    q->rear->next = newNode;
  }
  q->rear = newNode;
  if (q->front == NULL) {
    q->front = newNode;
  }
}

Entity dequeue(Queue *q) {
  if (q->front == NULL) {
    printf("ERROR: Queue is empty\n");
    Entity e = {0, 0};
    return e;
  }
  Node *popped = q->front;
  Entity data = popped->data;
  q->front = popped->next;
  if (q->front == NULL) {
    q->rear = NULL;
  }
  free(popped);
  return data;
}

int isEmpty(Queue *q) {
  return q->front == NULL;
}

void printQueue(Queue q) {
  Node *current = q.front;
  while (current != NULL) {
    printf("%d [%d] ", current->data.id, current->data.timestamp);
    current = current->next;
  }
  printf("\n");
}

void simulate() {
  Queue arrival, departure, processing;
  arrival.front = arrival.rear = NULL;
  departure.front = departure.rear = NULL;
  processing.front = processing.rear = NULL;

  int currentTimestamp = 0, id = 0;
  int arrivalCount = 0, departureCount = 0;
  while (arrivalCount < 10) {
    currentTimestamp++;
    if (rand() % 3 != 0) {
      // generate arrival event
      Entity entity = {++id, currentTimestamp};
      printf("Entity %d arrived at time %d\n", entity.id, entity.timestamp);
      enqueue(&arrival, entity);
      arrivalCount++;
    }
    if (departure.front && currentTimestamp >= departure.front->data.timestamp) {
      // departure event occurs before next arrival
      Entity entity = dequeue(&departure);
      printf("Entity %d departed at time %d\n", entity.id, entity.timestamp);
      departureCount++;
    } else if (arrival.front) {
      // process next arrival event
      Entity entity = dequeue(&arrival);
      printf("Entity %d entered processing queue at time %d\n", entity.id, entity.timestamp);
      enqueue(&processing, entity);
    }
    if (processing.front && !departure.front) {
      // start processing if queue not empty and no event scheduled
      Entity entity = dequeue(&processing);
      Entity nextDeparture = {entity.id, currentTimestamp + rand() % 5 + 1};
      printf("Entity %d started processing at time %d\n", entity.id, currentTimestamp);
      printf("Entity %d departure scheduled at time %d\n", entity.id, nextDeparture.timestamp);
      enqueue(&departure, nextDeparture);
    }
    printf("Simulation state:\n");
    printf("Arrival queue: ");
    printQueue(arrival);
    printf("Processing queue: ");
    printQueue(processing);
    printf("Departure queue: ");
    printQueue(departure);
    printf("-------------------------\n");
  }
  printf("Simulation ended\n");
}

int main() {
  srand(time(NULL));
  simulate();
  return 0;
}

以上是“C语言数据结构进阶之栈和队列的实现”的完整攻略。