文中代码基本都是由C语言实现，除了“2.3.4 Leetcode496”的代码实现。
1.队列
1.1 队列的性质
FIFO：Fist In, First Out，即先进先出。
队首出队，队尾出队。
1.2 普通队列
1.2.1 普通队列的代码实现
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
//普通队列，存在假溢出问题
typedef struct Queue {
int *data;
int head, tail;
int capacity;
} Queue;
/*
* 队列的初始化
*/
Queue *init(int n) {
Queue *que = (Queue *)malloc(sizeof(Queue));
que->data = (int *)malloc(sizeof(int) * n);
que->head = 0;
que->tail = 0;
que->capacity = n;
return que;
}
/*
* 返回队首元素
*/
int front(Queue *que) {
return que->data[que->head];
}
/*
* 判断队列是否为空
*/
int empty(Queue *que) {
return que->head == que->tail;
}
/*
* 入队
*/
int push(Queue *que, int val) {
if (que == NULL) return -1;
if (que->tail == que->capacity) { //判断队列是否满了
return -1;
}
que->data[que->tail++] = val;//先入队再更新tail值
return 0;
}
/*
* 出队
*/
int pop(Queue *que) {
if (que == NULL) return -1;
if (empty(que)) return -1;
que->head++;
return 0;
}
/*
* 队列元素的打印
*/
void output(Queue *que) {
printf("Queue : [");
for (int i = que->head, j = 0; i < que->tail; i++, j++) {
j && printf(", ");
printf("%d", que->data[i]);
}
printf("]\n");
return ;
}
/*
* 队列的销毁
*/
void clear(Queue *que) {
if (que == NULL) return ;
free(que->data);
free(que);
return ;
}
int main() {
srand(time(0));
#define max_op 20
Queue *que = init(max_op);
for (int i = 0; i < max_op * 2; i++) {
int val = rand() % 100;
int op = rand() % 4;
switch (op) {
case 0:
case 1:
case 2: {
printf("push %d to the Queue, result = %d\n", val, push(que, val));
} break;
case 3: {
printf("pop %d from the Queue, result = %d\n", front(que), pop(que));
} break;
}
output(que), printf("\n");
}
#undef max_op
clear(que);
return 0;
}
1.2.2 普通队列存在的问题
存在的问题：假溢出。
原因：因为入队时是判断tail 是否到 capacity - 1 ，如果 tail = capacity - 1，从逻辑上来说已经到了整个队列容量的最大，但是如果之前有出队操作，实际上队列前还能插入。
1.3 循环队列
为了解决普通队列的假溢出问题，出现了循环队列。
因为head 不一定在 tail 前面，新定义一个变量 count，记录循环队列中实际存储的元素个数。
1.3.1 循环队列的代码实现
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define COLOR(a, b) "\033[;" #b "m" a "\033[0m"
#define RED(a) COLOR(a, 31)
typedef struct Queue {
int *data;
int head;
int tail;
int count; //记录队列中已经存储的元素个数
int capacity;
} Queue;
/*
* 队列的初始化
*/
Queue *init(int n) {
Queue *que = (Queue *)malloc(sizeof(Queue));
que->data = (int *)malloc(sizeof(int) * n);
que->head = 0;
que->tail = 0;
que->count = 0;
que->capacity = n;
return que;
}
/*
* 返回队首元素
*/
int front(Queue *que) {
return que->data[que->head];
}
/*
* 判断队列是否为空
*/
int empty(Queue *que) {
return que->count == 0;
}
/*
* 入队
*/
int push(Queue *que, int val) {
if (que == NULL) return -1;
if (que->count == que->capacity) {
printf(RED("Queue is full!")"\n");
return -1;
}
que->data[que->tail++] = val;
if (que->tail == que->capacity) que->tail = 0;
que->count++;
return 0;
}
/*
* 出队
*/
int pop(Queue *que) {
if (que == NULL) return -1;
if (empty(que)) return -1;
que->head++;
if (que->head == que->capacity) que->head = 0;
que->count--;
return 0;
}
/*
* 队列元素的打印
*/
void output(Queue *que) {
printf("Queue : [");
for (int i = que->head, j = 0; j < que->count; j++, i++) {
j && printf(", ");
printf("%d", que->data[i % que->capacity]);
}
printf("]\n");
return ;
}
/*
* 队列的销毁
*/
void clear(Queue *que) {
if (que == NULL) return ;
free(que->data);
free(que);
return ;
}
int main() {
srand(time(0));
#define max_op 20
Queue *que = init(max_op / 2);
for (int i = 0; i < max_op; i++) {
int val = rand() % 100;
int op = rand() % 4;
switch (op) {
case 0:
case 1:
case 2: {
printf("push %d to the Queue, result = %d\n", val, push(que, val));
} break;
case 3: {
printf("pop %d from the Queue, result = %d\n", front(que), pop(que));
} break;
}
output(que), printf("\n");
}
#undef max_op
clear(que);
return 0;
}
1.3.2 循环队列的不足
当前实现的循环队列无法扩容，当循环队列满了之后，再插入元素就不行了。
1.3.3 循环队列扩容
循环队列扩容不建议使用realloc，因为指向队首元素的 head并不一定在指向队尾元素的 tail 的前面，循环队列中是严格按照 head 到 tail 的顺序进行输出的，但是内存排布中它们的顺序是不一定的。
推荐使用malloc或者 calloc，当开辟成功后，按照循环队列的原顺序拷贝到新的空间中，然后主动释放原来的空间。
int expand(Queue *q) { //队列扩容操作
int extr_size = q->length;
int *p;
while (extr_size) {
p = (int *)malloc(sizeof(int) * (q->length + extr_size));
if (p) break;
extr_size /= 2;
}
if (p == NULL) return 0;
//原队列中的值拷贝到新的空间，从head处的元素开始后拷贝，原head处的值放置到新空间的0下标处
for (int i = q->head, j = 0; j < q->count; j++) {
p[j] = q->data[(i + j) % q->length];
}
free(q->data);
q->data = p;
q->length += extr_size;
q->head = 0;
q->tail = q->count;
return 1;
}
//入队
int push(Queue *q, int val) {
if (q == NULL) return 0;
if (q->count == q->length) { //判断队列是否满了,满了进行扩容操作
if (!expand(q)) return 0;
printf(GREEN("Expand sucessfully!Queue->size(%d)") "\n", q->length);
}
//先入队，再更新tail的值
q->data[q->tail++] = val;
if (q->tail == q->length) q->tail = 0;
q->count++;
return 1;
}
完整代码：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define COLOR(a, b) "\033[" #b "m" a "\033[0m"
#define RED(a) COLOR(a, 31)
#define GREEN(a) COLOR(a, 32)
typedef struct Queue {
int *data;
int head;
int tail;
int count;
int capacity;
} Queue;
/*
* 队列的初始化
*/
Queue *init(int n) {
Queue *que = (Queue *)malloc(sizeof(Queue));
que->data = (int *)malloc(sizeof(int) * n);
que->head = 0;
que->tail = 0;
que->count = 0;
que->capacity = n;
return que;
}
/*
* 判断队列是否为空
*/
int empty(Queue *que) {
return que->count == 0;
}
/*
* 获取队首元素
*/
int front(Queue *que) {
return que->data[que->head];
}
/*
* 队列的扩容操作
*/
int expand(Queue *que) {
int extra_size = que->capacity;
int *p;
while (extra_size) {
p = (int *)malloc(sizeof(int) * (que->capacity + extra_size));
if (p) break;
extra_size /= 2;
}
if (p == NULL) return -1;
for (int i = que->head, j = 0; j < que->count; i++, j++) {
p[j] = que->data[(i + j) % que->capacity];
}
free(que->data);
que->data = p;
que->capacity += extra_size;
que->head = 0;
que->tail = que->count;
return 0;
}
/*
* 入队
*/
int push(Queue *que, int val) {
if (que == NULL) return -1;
if (que->count == que->capacity) { //若队列已满，进行扩容操作
if (expand(que) == -1) {
printf(RED("Expand queue fail!")"\n");
return -1;
}
printf(GREEN("Expand queue successfully! Queue->capacity(%d)") "\n", que->capacity);
}
que->data[que->tail++] = val;
if (que->tail == que->capacity) que->tail = 0;
que->count++;
return 0;
}
/*
* 出队
*/
int pop(Queue *que) {
if (que == NULL) return -1;
if (empty(que)) return -1;
que->head++;
if (que->head == que->capacity) que->head = 0;
que->count--;
return 0;
}
/*
* 队列元素的打印
*/
void output(Queue *que) {
printf("Queue : [");
for (int i = que->head, j = 0; j < que->count; i++, j++) {
j && printf(", ");
printf("%d", que->data[i % que->capacity]);
}
printf("]\n");
return ;
}
/*
* 队列的销毁
*/
void clear(Queue *que) {
if (que == NULL) return ;
free(que->data);
free(que);
return ;
}
int main() {
srand(time(0));
#define max_op 20
Queue *que = init(max_op / 4);
for (int i = 0; i < max_op; i++) {
int val = rand() % 100;
int op = rand() % 4;
switch (op) {
case 0:
case 1:
case 2: {
printf("push %d to the Queue, reuslt = %d\n", val, push(que, val));
} break;
case 3: {
printf("pop %d from the Queue, result = %d\n", front(que), pop(que));
} break;
}
output(que), printf("\n");
}
#undef max_op
clear(que);
return 0;
}
1.4 队列的应用
- 队列（循环）：树的层序遍历，广度优先搜索（图算法基础）
- 单调队列：区间最大（小）值
1.4.1 Leetcode 239. 滑动窗口最大值 —— 单调队列
求解的就是区间最大值，于是使用单调队列。
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize){
int que[numsSize]; //保存数组下标，下标对应的数组中的值是单调递减的
int head = 0, tail = 0;
for (int i = 0; i < k; i++) {
while (head < tail && nums[i] >= nums[que[tail - 1]]) {
tail--;
}
que[tail++] = i;
}
*returnSize = 0;
int *ret = malloc(sizeof(int) * (numsSize - k + 1));
ret[(*returnSize)++] = nums[que[head]];
for (int i = k; i < numsSize; i++) {
while (head < tail && nums[i] >= nums[que[tail - 1]]) {
tail--;
}
que[tail++] = i;
while (que[head] <= i - k) { //判断单调队列的队首元素是否在滑动窗口中
head++;
}
ret[(*returnSize)++] = nums[que[head]];
}
return ret;
}
2. 栈
2.1 栈的性质
FILO：First In，Last Out，即后进先出。
2.2 栈的代码实现
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct Stack {
int *data;
int capacity; //栈容量
int top; //栈顶指针
} Stack;
/*
* 栈的初始化
*/
Stack *init(int n) {
Stack *sta = (Stack *)malloc(sizeof(Stack));
sta->data = (int *)malloc(sizeof(int) * n);
sta->capacity = n;
sta->top = -1;
return sta;
}
/*
* 获取栈顶元素
*/
int top(Stack *sta) {
return sta->data[sta->top];
}
/*
* 判断栈是否为空
*/
int empty(Stack *sta) {
return sta->top == -1;
}
/*
* 入栈
*/
int push(Stack *sta, int val) {
if (sta == NULL) return -1;
if (sta->top == sta->capacity - 1) return -1;
sta->data[++(sta->top)] = val;
return 0;
}
/*
* 出栈
*/
int pop(Stack *sta) {
if (sta == NULL) return -1;
if (empty(sta)) return -1;
sta->top--;
return 0;
}
/*
* 栈内元素的打印
*/
void output(Stack *sta) {
printf("Stack(%d) = [", sta->top + 1);
for (int i = 0; i <= sta->top; i++) {
i && printf(", ");
printf("%d", sta->data[i]);
}
printf("]\n");
return ;
}
/*
* 栈的销毁
*/
void clear(Stack *sta) {
if (sta == NULL) return ;
free(sta->data);
free(sta);
return ;
}
int main() {
srand(time(0));
#define max_op 20
Stack *sta = init(max_op);
for (int i = 0; i < max_op; i++) {
int val = rand() % 100;
int op = rand() % 4;
switch (op) {
case 0:
case 1:
case 2: {
printf("push %d to the Stack, result = %d\n", val, push(sta, val));
} break;
case 3: {
printf("pop %d from the Stack, result = %d\n", top(sta), pop(sta));
} break;
}
output(sta), printf("\n");
}
#undef max_op
clear(sta);
return 0;
}
2.3 栈的应用
- 栈：树的深度遍历、深度优先搜索（图算法基础）
- 单调栈：临近最大（小）值
栈中存放的元素具有单调性，这就是经典的数据结构「单调栈」。
典型的单调栈的应用场景：一维数组中找到第一个满足某种条件的数。
2.3.1 Leetcode 20. 有效的括号
//数组实现栈
int getValue(char c) {
if (c == ')') return '(';
if (c == ']') return '[';
if (c == '}') return '{';
return 0;
}
bool isValid(char * s){
int sta[strlen(s) + 1], top = 0;
for (int i = 0; s[i]; i++) {
int ch = getValue(s[i]);
if (ch) {
if (top == 0 || sta[top - 1] != ch)
return false;
top--;
} else {
sta[top++] = s[i];
}
}
return top == 0;
}
2.3.2 Leetcode 42.接雨水 —— 单调栈
//找到每个柱子左边第一个高于它的和右边第一个高于它的柱子（临近最大值）
//时间复杂度O(n)
int trap(int* height, int heightSize) {
int n = heightSize;
if (n == 0) {
return 0;
}
int ans = 0;
int stk[n], top = 0;
for (int i = 0; i < n; ++i) {
while (top && height[i] > height[stk[top - 1]]) {
int stk_top = stk[--top];
if (!top) {
break;
}
int left = stk[top - 1];
int currWidth = i - left - 1;
int currHeight = fmin(height[left], height[i]) - height[stk_top];
ans += currWidth * currHeight;
}
stk[top++] = i;
}
return ans;
}
2.3.3 Leetcode 84.柱状图中最大的矩形 —— 单调栈 + 常数优化
int largestRectangleArea(int* heights, int heightsSize){
int n = heightsSize;
int left[n], right[n];
int ans = 0;
int mono_stack[n], top = -1;
//分别找到并记录每根柱子左侧和右侧第一个小于该柱子高度的位置
for (int i = 0; i < n; i++) {
right[i] = n;
while (top != -1 && heights[mono_stack[top]] >= heights[i]) {
right[mono_stack[top]] = i; //栈顶位置的右侧第一个小于该高度的就是i位置的柱子
top--;
}
left[i] = top == -1 ? -1 : mono_stack[top];
mono_stack[++top] = i;
}
for (int i = 0; i < n; i++) {
ans = fmax(ans, (right[i] - left[i] - 1) * heights[i]);
}
return ans;
}
2.3.4 Leetcode 496.下一个更大元素I —— 单调栈 + 哈希表
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
vector<int> ans;
stack<int> mono_stack;
unordered_map<int, int> ans_map;
int n = nums1.size(), m = nums2.size();
for (int i = 0; i < m; i++) {
ans_map[nums2[i]] = -1;
//单调栈保存nums2数组每个数右边第一个大于该数的数
while (!mono_stack.empty() && nums2[i] > mono_stack.top()) {
ans_map[mono_stack.top()] = nums2[i];
mono_stack.pop();
}
mono_stack.push(nums2[i]);
}
for (int i = 0; i < n; i++) {
ans.push_back(ans_map[nums1[i]]);
}
return ans;
}
};
2.3.5 Leetcode 503.下一个更大元素II —— 单调栈 + 循环数组
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* nextGreaterElements(int* nums, int numsSize, int* returnSize){
*returnSize = numsSize;
if (numsSize == 0) return NULL;
int *res = (int *)malloc(sizeof(int) * numsSize);
memset(res, -1, sizeof(int) * numsSize);
//sta存储下标,利用取模的方式处理循环数组
int sta[numsSize * 2], top = 0;
for (int i = 0; i < numsSize * 2 - 1; i++) {
while (top > 0 && nums[sta[top - 1]] < nums[i % numsSize]) {
res[sta[top - 1]] = nums[i % numsSize];
top--;
}
sta[top++] = i % numsSize;
}
return res;
}
2.3.6 Leetcode 739.每日温度 —— 单调栈
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* nextGreaterElements(int* nums, int numsSize, int* returnSize){
*returnSize = numsSize;
if (numsSize == 0) return NULL;
int *res = (int *)malloc(sizeof(int) * numsSize);
memset(res, -1, sizeof(int) * numsSize);
//sta存储下标,利用取模的方式处理循环数组
int sta[numsSize * 2], top = 0;
for (int i = 0; i < numsSize * 2 - 1; i++) {
while (top > 0 && nums[sta[top - 1]] < nums[i % numsSize]) {
res[sta[top - 1]] = nums[i % numsSize];
top--;
}
sta[top++] = i % numsSize;
}
return res;
}
2.3.7 Leetcode 1673.找出最具竞争力的子序列 —— 单调栈
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* mostCompetitive(int* nums, int numsSize, int k, int* returnSize){
*returnSize = k;
if (numsSize == 0) return NULL;
int n = numsSize;
int sta[n], top = 0;
int *ret = (int *)malloc(sizeof(int) * k);
int removeCount = n - k;
for (int i = 0; i < n; i++) {
while (removeCount > 0 && top && nums[i] < nums[sta[top - 1]]) {
removeCount--;
top--;
}
sta[top++] = i;
}
//此时单调栈中保存的数组下标对应的数据从栈底到栈顶是单调递增的
//从栈底开始的k个元素就是最终的答案
while (removeCount--) {
--top;
}
int ind = k - 1;
while (ind >= 0 && top) {
ret[ind--] = nums[sta[top - 1]];
top--;
}
return ret;
}
3. Leetcode 225. 用队列实现栈
思路：一个队列即可，新元素入队后，队列中该元素前的元素依次出队并再次入队。
//用数组实现队列
typedef struct {
int *data;
int head;
int tail;
int length;
int capacity;
} MyStack;
/** Initialize your data structure here. */
MyStack* myStackCreate() {
MyStack *sta = (MyStack *)malloc(sizeof(MyStack));
sta->data = (int *)malloc(sizeof(int) * 100);
sta->head = 0;
sta->tail = 0;
sta->length = 0;
sta->capacity = 100;
return sta;
}
/** Push element x onto stack. */
void myStackPush(MyStack* obj, int x) {
//if (obj->tail == obj->capacity) obj->tail = 0;
obj->data[obj->tail++] = x;
int n = obj->length;
while (n--) {
obj->data[obj->tail++] = obj->data[obj->head];
obj->head++;
}
obj->length++;
}
/** Removes the element on top of the stack and returns that element. */
int myStackPop(MyStack* obj) {
if (obj->length == 0) return -1;
int data = obj->data[obj->head++];
obj->length--;
return data;
}
/** Get the top element. */
int myStackTop(MyStack* obj) {
return obj->data[obj->head];
}
/** Returns whether the stack is empty. */
bool myStackEmpty(MyStack* obj) {
return obj->length == 0;
}
void myStackFree(MyStack* obj) {
if (obj == NULL) return ;
free(obj->data);
free(obj);
return ;
}
/**
* Your MyStack struct will be instantiated and called as such:
* MyStack* obj = myStackCreate();
* myStackPush(obj, x);
* int param_2 = myStackPop(obj);
* int param_3 = myStackTop(obj);
* bool param_4 = myStackEmpty(obj);
* myStackFree(obj);
*/
用链表实现队列，然后采用头插法：
typedef struct tagLinkNode {
int val;
struct tagLinkNode *next;
} LinkNode;
typedef struct {
LinkNode *top;
} MyStack;
/** Initialize your data structure here. */
MyStack* myStackCreate() {
MyStack *stk = calloc(1, sizeof(MyStack));
return stk;
}
/** Push element x onto stack. */
void myStackPush(MyStack* obj, int x) {
LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));
node->val = x;
node->next = obj->top;
obj->top = node;
return ;
}
/** Removes the element on top of the stack and returns that element. */
int myStackPop(MyStack* obj) {
if (obj->top == NULL) return -1;
LinkNode *node = obj->top;
int data = node->val;
obj->top = node->next;
free(node);
return data;
}
/** Get the top element. */
int myStackTop(MyStack* obj) {
return obj->top ? obj->top->val : -1;
}
/** Returns whether the stack is empty. */
bool myStackEmpty(MyStack* obj) {
return (obj->top) == NULL;
}
void myStackFree(MyStack* obj) {
while (obj->top != NULL) {
LinkNode *node = obj->top;
obj->top = node->next;
free(node);
}
return ;
}
/**
* Your MyStack struct will be instantiated and called as such:
* MyStack* obj = myStackCreate();
* myStackPush(obj, x);
* int param_2 = myStackPop(obj);
* int param_3 = myStackTop(obj);
* bool param_4 = myStackEmpty(obj);
* myStackFree(obj);
*/
4. Leetcode 232. 用栈实现队列
思路：双栈，一个输入栈(处理push），一个输出栈（处理pop和peek)
//C语言自己实现栈并应用
typedef struct {
int *data;
int top;
int capacity;
} Stack;
Stack *stackCreate(int capacity) {
Stack *sta = malloc(sizeof(Stack));
sta->data = malloc(sizeof(int) * capacity);
sta->top = -1;
sta->capacity = capacity;
return sta;
}
void stackPush(Stack *obj, int x) {
obj->data[++(obj->top)] = x;
}
void stackPop(Stack *obj) {
obj->top--;
}
int stackTop(Stack *obj) {
return obj->data[obj->top];
}
bool stackEmpty(Stack *obj) {
return obj->top == -1;
}
void stackFree(Stack *obj) {
if (obj == NULL) return ;
free(obj->data);
free(obj);
return ;
}
typedef struct {
Stack *inStack;
Stack *outStack;
} MyQueue;
/** Initialize your data structure here. */
MyQueue* myQueueCreate() {
MyQueue *que = malloc(sizeof(MyQueue));
que->inStack = stackCreate(100);
que->outStack = stackCreate(100);
return que;
}
/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {
stackPush(obj->inStack, x);
}
void in2out(MyQueue *obj) {
while (!stackEmpty(obj->inStack)) {
stackPush(obj->outStack, stackTop(obj->inStack));
stackPop(obj->inStack);
}
}
/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {
if (stackEmpty(obj->outStack)) {
in2out(obj);
}
int x = stackTop(obj->outStack);
stackPop(obj->outStack);
return x;
}
/** Get the front element. */
int myQueuePeek(MyQueue* obj) {
if (stackEmpty(obj->outStack)) {
in2out(obj);
}
return stackTop(obj->outStack);
}
/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj) {
return stackEmpty(obj->inStack) && stackEmpty(obj->outStack);
}
void myQueueFree(MyQueue* obj) {
stackFree(obj->inStack);
stackFree(obj->outStack);
}
/**
* Your MyQueue struct will be instantiated and called as such:
* MyQueue* obj = myQueueCreate();
* myQueuePush(obj, x);
* int param_2 = myQueuePop(obj);
* int param_3 = myQueuePeek(obj);
* bool param_4 = myQueueEmpty(obj);
* myQueueFree(obj);
*/