网站运营优化_建筑网片是干什么用的_广州seo工作_网页设计个人主页模板

栈和队列

1 栈

1.1 栈的结构体定义

typedef struct {ElemType *data;int top; int capacity;
} Stack;

data：指向动态数组的指针，用于存储栈中的元素。
top：栈顶指针，表示当前栈中元素的数量，同时也指向下一个入栈的位置。
capacity：栈的当前容量，当栈满时会动态扩容。

1.2 基本功能实现

1.2.1 创建栈

Stack *create_stack(int size) {Stack *stk = (Stack *)malloc(sizeof(Stack));stk->capacity = size;stk->top = 0;stk->data = (ElemType *)malloc(stk->capacity * sizeof(ElemType));return stk;
}

功能：初始化一个栈，分配指定大小的内存空间。
参数：size 表示栈的初始容量。
返回值：指向新创建的栈的指针。

1.2.2 销毁栈

void destroy_stack(Stack *stk) {if (stk) {free(stk->data);  // 释放动态数组free(stk);        // 释放栈结构体stk = NULL;       // 将指针置为 NULL，避免野指针}
}

功能：释放栈占用的内存，防止内存泄漏。
注意：在释放内存后，将栈指针置为 NULL，避免野指针问题。

1.2.3 入栈

void push(Stack *stk, ElemType b) {if (stk->top >= stk->capacity) {// 栈满扩展容量stk->capacity <<= 1;  // 容量翻倍stk->data = (ElemType *)realloc(stk->data, stk->capacity * sizeof(ElemType));}stk->data[stk->top++] = b;  // 将元素放入栈顶，并更新栈顶指针
}

功能：将元素压入栈顶。
动态扩容：当栈满时，容量翻倍，并通过 realloc 重新分配内存。

1.2.4 出栈

ElemType pop(Stack *stk) {if (stk->top <= 0) {return ERROR;  // 栈为空时返回错误值}return stk->data[--stk->top];  // 返回栈顶元素，并更新栈顶指针
}

功能：弹出栈顶元素。
返回值：栈顶元素；如果栈为空，返回预定义的错误值 ERROR。

1.2.5 判断栈是否为空

int is_empty(Stack *stk) {return stk->top == 0;
}

功能：判断栈是否为空。
返回值：如果栈为空，返回 1；否则返回 0。

1.2.6 获取栈顶元素（不弹出）

ElemType peek(Stack *stk) {if (stk->top <= 0) {return ERROR;  // 栈为空时返回错误值}return stk->data[stk->top - 1];  // 返回栈顶元素
}

功能：获取栈顶元素，但不弹出。
返回值：栈顶元素；如果栈为空，返回预定义的错误值 ERROR。

1.2.7 获取栈的当前大小

int get_stack_size(Stack *stk) {return stk->top;
}

功能：获取栈中当前元素的数量。
返回值：栈的大小。

1.3 代码实现

注意，代码省略了头文件和主函数，只包含和栈相关的代码，其中 ERROR 是需要用户自定义的错误值，其类型由 ElemType 决定，这里只是示例，将 ElemType 设为 int。

#define ERROR -114514
typedef int ElemType;typedef struct {ElemType *data;int top;int capacity;
} Stack;// 创建栈
Stack *create_stack(int size) {Stack *stk = (Stack *)malloc(sizeof(Stack));// 注意这里并没有添加内存分配失败的处理stk->capacity = size;stk->top = 0;stk->data = (ElemType *)malloc(stk->capacity * sizeof(ElemType));return stk;
}// 销毁栈
void destroy_stack(Stack *stk) {if (stk) {free(stk->data);free(stk);stk = NULL;}
}// 入栈
void push(Stack *stk, ElemType b) {if (stk->top >= stk->capacity) {// 栈满扩展容量，这里并没有考虑整数溢出stk->capacity <<= 1;// 注意这里并没有添加内存分配失败的处理stk->data = (ElemType *)realloc(stk->data, stk->capacity * sizeof(ElemType));}stk->data[stk->top++] = b;
}// 出栈
ElemType pop(Stack *stk) {if (stk->top <= 0) {return ERROR;}return stk->data[--stk->top];
}// 判断栈是否为空
int is_empty(Stack *stk) { return stk->top == 0; }// 获取栈顶元素（不弹出）
ElemType peek(Stack *stk) {if (stk->top <= 0) {return ERROR;}return stk->data[stk->top - 1];
}// 获取栈的当前大小
int get_stack_size(Stack *stk) { return stk->top; }

2 队列

这里实现一个循环队列

2.1 循环队列的结构体定义

typedef struct {ElemType *data;int front;int rear;int capacity;
} CircularQueue;

data：指向动态数组的指针，用于存储队列中的元素。
front：队头指针，指向队列的第一个元素。
rear：队尾指针，指向队列的最后一个元素的下一个位置。
capacity：队列的当前容量，队列的实际可用容量为 capacity - 1，因为需要区分队列满和队列空的情况。

2.2 基本功能实现

2.2.1 创建循环队列

CircularQueue *create_circular_queue(int size) {CircularQueue *queue = (CircularQueue *)malloc(sizeof(CircularQueue));queue->capacity = size + 1;  // 多分配一个空间用于区分队列满和队列空queue->front = 0;queue->rear = 0;queue->data = (ElemType *)malloc(queue->capacity * sizeof(ElemType));return queue;
}

功能：初始化一个循环队列，分配指定大小的内存空间。
参数：size 表示队列的初始容量。
返回值：指向新创建的循环队列的指针。

2.2.2 销毁循环队列

void destroy_circular_queue(CircularQueue *queue) {if (queue) {free(queue->data);  // 释放动态数组free(queue);        // 释放队列结构体queue = NULL;       // 将指针置为 NULL，避免野指针}
}

功能：释放循环队列占用的内存，防止内存泄漏。
注意：在释放内存后，将队列指针置为 NULL，避免野指针问题。

2.2.3 入队

void enqueue(CircularQueue *queue, ElemType b) {if ((queue->rear + 1) % queue->capacity == queue->front) {// 队列满，扩展容量int new_capacity = queue->capacity * 2;ElemType *new_data = (ElemType *)malloc(new_capacity * sizeof(ElemType));int i = 0;while (queue->front != queue->rear) {new_data[i++] = queue->data[queue->front];queue->front = (queue->front + 1) % queue->capacity;}free(queue->data);queue->data = new_data;queue->front = 0;queue->rear = i;queue->capacity = new_capacity;}queue->data[queue->rear] = b;queue->rear = (queue->rear + 1) % queue->capacity;
}

功能：将元素插入队尾。
动态扩容：当队列满时，容量翻倍，并重新分配内存。

2.2.4 出队

ElemType dequeue(CircularQueue *queue) {if (queue->front == queue->rear) {return ERROR;  // 队列为空时返回错误值}ElemType elem = queue->data[queue->front];queue->front = (queue->front + 1) % queue->capacity;return elem;
}

功能：删除队头元素并返回。
返回值：队头元素；如果队列为空，返回预定义的错误值 ERROR。

2.2.5 判断队列是否为空

int is_empty(CircularQueue *queue) {return queue->front == queue->rear;
}

功能：判断队列是否为空。
返回值：如果队列为空，返回 1；否则返回 0。

2.2.6 获取队头元素（不删除）

ElemType peek_front(CircularQueue *queue) {if (queue->front == queue->rear) {return ERROR;  // 队列为空时返回错误值}return queue->data[queue->front];
}

功能：获取队头元素，但不删除。
返回值：队头元素；如果队列为空，返回预定义的错误值 ERROR。

2.2.7 获取队列的当前大小

int get_queue_size(CircularQueue *queue) {return (queue->rear - queue->front + queue->capacity) % queue->capacity;
}

功能：获取队列中当前元素的数量。
返回值：队列的大小。

2.3 代码实现

注意，代码省略了头文件和主函数，只包含和循环队列相关的代码，其中 ERROR 是需要用户自定义的错误值，其类型由 ElemType 决定，这里只是示例，将 ElemType 设为 int。

#define ERROR -114514
typedef int ElemType;typedef struct {ElemType *data;int front;int rear;int capacity;
} CircularQueue;// 创建循环队列
CircularQueue *create_circular_queue(int size) {CircularQueue *queue = (CircularQueue *)malloc(sizeof(CircularQueue));queue->capacity = size + 1;  // 多分配一个空间用于区分队列满和队列空queue->front = 0;queue->rear = 0;queue->data = (ElemType *)malloc(queue->capacity * sizeof(ElemType));return queue;
}// 销毁循环队列
void destroy_circular_queue(CircularQueue *queue) {if (queue) {free(queue->data);free(queue);queue = NULL;}
}// 入队
void enqueue(CircularQueue *queue, ElemType b) {if ((queue->rear + 1) % queue->capacity == queue->front) {// 队列满，扩展容量int new_capacity = queue->capacity * 2;ElemType *new_data = (ElemType *)malloc(new_capacity * sizeof(ElemType));int i = 0;while (queue->front != queue->rear) {new_data[i++] = queue->data[queue->front];queue->front = (queue->front + 1) % queue->capacity;}free(queue->data);queue->data = new_data;queue->front = 0;queue->rear = i;queue->capacity = new_capacity;}queue->data[queue->rear] = b;queue->rear = (queue->rear + 1) % queue->capacity;
}// 出队
ElemType dequeue(CircularQueue *queue) {if (queue->front == queue->rear) {return ERROR;  // 队列为空时返回错误值}ElemType elem = queue->data[queue->front];queue->front = (queue->front + 1) % queue->capacity;return elem;
}// 判断队列是否为空
int is_empty(CircularQueue *queue) {return queue->front == queue->rear;
}// 获取队头元素（不删除）
ElemType peek_front(CircularQueue *queue) {if (queue->front == queue->rear) {return ERROR;  // 队列为空时返回错误值}return queue->data[queue->front];
}// 获取队列的当前大小
int get_queue_size(CircularQueue *queue) {return (queue->rear - queue->front + queue->capacity) % queue->capacity;
}

3 总结

实际上，如果是算法题用纯 C 语言的话，根本不需要将这些数据结构提出来封装，都是直接使用数组在逻辑上模拟的而且谁在做题的时候用纯 C 语言啊。以上作为使用 C 语言实现栈和队列的参考。