辽宁建设厅网站监管处cfa三级和一二级关系大吗

1. 栈（Stack）

1.1 栈的定义

栈是一种后进先出（Last In First Out, LIFO）的数据结构。栈中元素的插入和删除只在一端进行，该端称为栈顶（Top）。

1.2 栈的基本操作

• 入栈（Push）：将元素添加到栈顶。
• 出栈（Pop）：从栈顶移除元素。
• 栈顶元素（Peek/Top）：返回栈顶的元素，但不移除。
• 检查栈是否为空（IsEmpty）：检查栈中是否有元素。

1.3 栈的实现

栈可以使用数组或链表来实现。

使用数组实现栈

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MAX_SIZE 100typedef struct {int items[MAX_SIZE];int top;
} Stack;void init_stack(Stack* stack) {stack->top = -1;
}bool is_empty(Stack* stack) {return stack->top == -1;
}bool is_full(Stack* stack) {return stack->top == MAX_SIZE - 1;
}void push(Stack* stack, int item) {if (is_full(stack)) {printf("Stack Overflow\n");return;}stack->items[++stack->top] = item;
}int pop(Stack* stack) {if (is_empty(stack)) {printf("Stack Underflow\n");return -1;}return stack->items[stack->top--];
}int peek(Stack* stack) {if (is_empty(stack)) {printf("Stack is empty\n");return -1;}return stack->items[stack->top];
}

使用链表实现栈

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>typedef struct Node {int value;struct Node* next;
} Node;typedef struct {Node* top;
} Stack;void init_stack(Stack* stack) {stack->top = NULL;
}bool is_empty(Stack* stack) {return stack->top == NULL;
}void push(Stack* stack, int value) {Node* new_node = (Node*)malloc(sizeof(Node));new_node->value = value;new_node->next = stack->top;stack->top = new_node;
}int pop(Stack* stack) {if (is_empty(stack)) {printf("Stack Underflow\n");return -1;}Node* temp = stack->top;int value = temp->value;stack->top = stack->top->next;free(temp);return value;
}int peek(Stack* stack) {if (is_empty(stack)) {printf("Stack is empty\n");return -1;}return stack->top->value;
}

1.4 栈的应用

• 函数调用栈：用于跟踪函数调用和返回。
• 表达式求值：用于中缀表达式转后缀表达式、表达式求值。
• 括号匹配：用于检查括号是否匹配。

2. 队列（Queue）

2.1 队列的定义

队列是一种先进先出（First In First Out, FIFO）的数据结构。队列中元素的插入在一端进行，该端称为队尾（Rear），删除在另一端进行，该端称为队头（Front）。

2.2 队列的基本操作

• 入队（Enqueue）：将元素添加到队尾。
• 出队（Dequeue）：从队头移除元素。
• 队头元素（Peek/Front）：返回队头的元素，但不移除。
• 检查队列是否为空（IsEmpty）：检查队列中是否有元素。

2.3 队列的实现

队列可以使用数组或链表来实现。

使用数组实现队列

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MAX_SIZE 100typedef struct {int items[MAX_SIZE];int front;int rear;
} Queue;void init_queue(Queue* queue) {queue->front = -1;queue->rear = -1;
}bool is_empty(Queue* queue) {return queue->front == -1;
}bool is_full(Queue* queue) {return queue->rear == MAX_SIZE - 1;
}void enqueue(Queue* queue, int item) {if (is_full(queue)) {printf("Queue Overflow\n");return;}if (queue->front == -1)queue->front = 0;queue->items[++queue->rear] = item;
}int dequeue(Queue* queue) {if (is_empty(queue)) {printf("Queue Underflow\n");return -1;}int item = queue->items[queue->front];if (queue->front >= queue->rear) {queue->front = -1;queue->rear = -1;} else {queue->front++;}return item;
}int peek(Queue* queue) {if (is_empty(queue)) {printf("Queue is empty\n");return -1;}return queue->items[queue->front];
}

使用链表实现队列

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>typedef struct Node {int value;struct Node* next;
} Node;typedef struct {Node* front;Node* rear;
} Queue;void init_queue(Queue* queue) {queue->front = NULL;queue->rear = NULL;
}bool is_empty(Queue* queue) {return queue->front == NULL;
}void enqueue(Queue* queue, int value) {Node* new_node = (Node*)malloc(sizeof(Node));new_node->value = value;new_node->next = NULL;if (queue->rear) {queue->rear->next = new_node;}queue->rear = new_node;if (queue->front == NULL) {queue->front = new_node;}
}int dequeue(Queue* queue) {if (is_empty(queue)) {printf("Queue Underflow\n");return -1;}Node* temp = queue->front;int value = temp->value;queue->front = queue->front->next;if (queue->front == NULL) {queue->rear = NULL;}free(temp);return value;
}int peek(Queue* queue) {if (is_empty(queue)) {printf("Queue is empty\n");return -1;}return queue->front->value;
}

2.4 队列的应用

• 操作系统中的任务调度：用于管理进程和任务调度。
• 广度优先搜索（BFS）：用于图的遍历。
• 缓冲区：用于数据缓冲和流处理。

3. 栈与队列的比较

特性	栈（Stack）	队列（Queue）
数据结构	后进先出（LIFO）	先进先出（FIFO）
基本操作	Push, Pop, Peek, IsEmpty	Enqueue, Dequeue, Peek, IsEmpty
插入位置	栈顶	队尾
删除位置	栈顶	队头
应用场景	函数调用栈、表达式求值、括号匹配	任务调度、广度优先搜索、缓冲区
实现方式	数组或链表	数组或链表