《栈和队列学习笔记》

栈及其结构定义

栈（Stack）是一种重要的线性数据结构，它具有以下主要结构性质和特性：

1. 后进先出（LIFO, Last In First Out）

基本性质：栈是一种后进先出的数据结构，即最后插入的元素最先被删除。
操作：
- 入栈（Push）：将一个元素压入栈顶。
- 出栈（Pop）：从栈顶移除一个元素。

2. 栈的基本操作

Push：在栈顶插入一个元素。
Pop：移除并返回栈顶的元素。
Peek/Top：返回栈顶的元素但不移除它。
IsEmpty：检查栈是否为空。
IsFull（对于有固定大小的栈）：检查栈是否已满。

3. 栈的实现方式

数组实现：

顺序存储：使用数组来存储栈中的元素。
固定大小：需要预先定义栈的最大容量。
访问效率高：栈顶元素的访问和操作时间复杂度为O(1)。

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

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

// 初始化栈
void initStack(Stack *s) {
    s->top = -1;
}

// 入栈操作
int push(Stack *s, int value) {
    if (s->top == MAX_SIZE - 1) {
        printf("Stack overflow\\n");
        return 0;
    }
    s->data[++(s->top)] = value;
    return 1;
}

// 出栈操作
int pop(Stack *s, int *value) {
    if (s->top == -1) {
        printf("Stack underflow\\n");
        return 0;
    }
    *value = s->data[(s->top)--];
    return 1;
}

// 取栈顶元素
int peek(Stack *s, int *value) {
    if (s->top == -1) {
        printf("Stack is empty\\n");
        return 0;
    }
    *value = s->data[s->top];
    return 1;
}

// 检查栈是否为空
int isEmpty(Stack *s) {
    return s->top == -1;
}

链表实现：

链式存储：使用链表来存储栈中的元素。
动态大小：不需要预先定义栈的最大容量，栈的大小可以动态变化。
灵活性高：适用于需要频繁改变栈大小的场景。

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

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

typedef struct {
    Node *top;
} Stack;

// 初始化栈
void initStack(Stack *s) {
    s->top = NULL;
}

// 入栈操作
int push(Stack *s, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Stack overflow\\n");
        return 0;
    }
    newNode->data = value;
    newNode->next = s->top;
    s->top = newNode;
    return 1;
}

// 出栈操作
int pop(Stack *s, int *value) {
    if (s->top == NULL) {
        printf("Stack underflow\\n");
        return 0;
    }
    Node *temp = s->top;
    *value = temp->data;
    s->top = s->top->next;
    free(temp);
    return 1;
}

// 取栈顶元素
int peek(Stack *s, int *value) {
    if (s->top == NULL) {
        printf("Stack is empty\\n");
        return 0;
    }
    *value = s->top->data;
    return 1;
}

// 检查栈是否为空
int isEmpty(Stack *s) {
    return s->top == NULL;
}

4. 应用场景

函数调用管理：函数调用栈用于管理函数的调用和返回，保存函数的局部变量和返回地址。
表达式求值和语法解析：用于计算机编译器中表达式求值、语法解析等。
撤销操作：应用程序中的撤销操作（如文本编辑器中的撤销功能）使用栈来保存历史操作。
深度优先搜索（DFS）：在图的深度优先搜索算法中使用栈来保存访问路径。

5. 栈的优缺点

优点：
- 简单且高效，适用于需要后进先出（LIFO）顺序的操作。
- 动态链表实现可以灵活调整大小，节省空间。
缺点：
- 不支持随机访问，访问栈底元素需要O(n)时间。
- 数组实现需要预先定义最大容量，可能浪费空间或出现溢出。

栈代码实现

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

typedef struct Stack {
    int *data;
    int size, top;
} Stack;

Stack *initStack(int n) {
    Stack *s = (Stack *)malloc(sizeof(Stack));
    s->data = (int *)malloc(sizeof(int) * n);
    s->size = n;
    s->top  = -1;
    return s;
}

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

int top(Stack *s) {
    if (empty(s)) return 0;
    return s->data[s->top];
}

int push(Stack *s, int val) {
    if (s->top + 1 == s->size) return 0;
    s->top += 1;
    s->data[s->top] = val;
    return 1;
}

int pop(Stack *s) {
    if (empty(s)) return 0;
    s->top -= 1;
    return 1;
} 

void clearStack(Stack *s) {
    if (s == NULL) return ;
    free(s->data);
    free(s);
    return ;
}

void outputStack(Stack *s) {
    printf("Stack : ");
    for (int i = s->top; i >= 0; --i) {
        printf("%4d", s->data[i]);
    }
    printf("\n\n");
    return ;
}

int main() {
    #define MAX_OP 10 
    srand(time(0));
    Stack *s = initStack(10);
    for (int i = 0; i < MAX_OP; i++) {
        int op = rand() % 3, val = rand() % 100;
        switch (op) {
            case 0:
                printf("pop stack, item = %d\n", top(s));
                pop(s);
                break;
            case 1:
            case 2:
                printf("push stack, item = %d\n", val);
                push(s, val);
                break;
        }
        outputStack(s);
    }
    clearStack(s);
    return 0;
}

队列及其结构定义

队列（Queue）是一种常用的线性数据结构，具有先进先出（FIFO, First In First Out）的特性。以下是队列的基本性质和相关特性：

1. 先进先出（FIFO）

基本性质：队列是一种先进先出的数据结构，即最先进入队列的元素最先被删除。
操作：
- 入队（Enqueue）：在队列的末尾插入一个元素。
- 出队（Dequeue）：从队列的开头删除一个元素。

2. 队列的基本操作

Enqueue：在队列的尾部添加一个元素。
Dequeue：移除并返回队列头部的元素。
Front/Peek：返回队列头部的元素但不移除它。
IsEmpty：检查队列是否为空。
IsFull（对于有固定大小的队列）：检查队列是否已满。

3. 队列的实现方式

数组实现：

顺序存储：使用数组来存储队列中的元素。
循环队列：为了避免浪费空间，通常采用循环队列的方式，通过取模运算实现队列的循环。

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
    int size;
} Queue;

// 初始化队列
void initQueue(Queue *q) {
    q->front = 0;
    q->rear = 0;
    q->size = 0;
}

// 检查队列是否为空
int isEmpty(Queue *q) {
    return q->size == 0;
}

// 检查队列是否已满
int isFull(Queue *q) {
    return q->size == MAX_SIZE;
}

// 入队操作
int enqueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("Queue overflow\\n");
        return 0;
    }
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % MAX_SIZE;
    q->size++;
    return 1;
}

// 出队操作
int dequeue(Queue *q, int *value) {
    if (isEmpty(q)) {
        printf("Queue underflow\\n");
        return 0;
    }
    *value = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    q->size--;
    return 1;
}

// 返回队列头部元素
int peek(Queue *q, int *value) {
    if (isEmpty(q)) {
        printf("Queue is empty\\n");
        return 0;
    }
    *value = q->data[q->front];
    return 1;
}

链表实现：

链式存储：使用链表来存储队列中的元素。
动态大小：不需要预先定义队列的最大容量，队列的大小可以动态变化。

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

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

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

// 初始化队列
void initQueue(Queue *q) {
    q->front = q->rear = NULL;
}

// 检查队列是否为空
int isEmpty(Queue *q) {
    return q->front == NULL;
}

// 入队操作
int enqueue(Queue *q, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Queue overflow\\n");
        return 0;
    }
    newNode->data = value;
    newNode->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
    return 1;
}

// 出队操作
int dequeue(Queue *q, int *value) {
    if (isEmpty(q)) {
        printf("Queue underflow\\n");
        return 0;
    }
    Node *temp = q->front;
    *value = temp->data;
    q->front = q->front->next;
    if (q->front == NULL) {
        q->rear = NULL;
    }
    free(temp);
    return 1;
}

// 返回队列头部元素
int peek(Queue *q, int *value) {
    if (isEmpty(q)) {
        printf("Queue is empty\\n");
        return 0;
    }
    *value = q->front->data;
    return 1;
}

4. 队列的应用场景

操作系统中的进程调度：操作系统使用队列来管理进程的调度。
广度优先搜索（BFS）：在图的广度优先搜索算法中使用队列来保存访问路径。
打印队列：打印作业通常按照先来先服务的顺序进行处理。
缓冲区：在网络通信、I/O操作等场景中，使用队列作为缓冲区来临时存储数据。

5. 队列的优缺点

优点：
- 简单且高效，适用于需要先进先出（FIFO）顺序的操作。
- 动态链表实现可以灵活调整大小，节省空间。
缺点：
- 不支持随机访问，访问队列中任意位置的元素需要O(n)时间。
- 数组实现的队列如果不使用循环队列，可能会浪费空间。

队列代码实现

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

typedef struct vector {
    int *data;
    int size;
}vector;

typedef struct Queue {
    vector *data;
    int size, head, tail, count;
} Queue;

vector *initVector(int n) {
    vector *v = (vector *)malloc(sizeof(vector));
    v->size = n;
    v->data = (int *)malloc(sizeof(int) * n);
    return v;
}

int vectorSeek(vector *v, int pos) {
    if (pos < 0 || pos >= v->size) return -1;
    return v->data[pos];
}

int insertVector(vector *v, int pos, int val) {
    if (pos < 0 || pos >= v->size) return 0;
    return v->data[pos] = val;
}

void clearVector(vector *v) {
    if (v == NULL) return ;
    free(v->data);
    free(v);
    return ;
}

Queue *initQueue(int n) {
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->data = initVector(n);
    q->size = n;
    q->head = q->tail = q->count = 0;
    return q;
}

int empty(Queue *q) {
    return q->count == 0;
}

int push(Queue *q, int val) {
    if (q->count == q->size) return 0;
    insertVector(q->data, q->tail, val);
    q->tail += 1;
    if (q->tail == q->size) q->tail = 0;
    q->count += 1;
    return 1;
}

int front(Queue *q) { 
    return vectorSeek(q->data, q->head);
}

int pop(Queue *q) {
    if (empty(q)) return 0;
    q->head += 1;
    if (q->head == q->size) q->head = 0;
    q->count -= 1;
    return 1;
}

void clearQueue(Queue *q) {
    if (q == NULL) return ;
    clearVector(q->data);
    free(q);
    return ;
}

void outputQueue(Queue *q) {
    printf("Queue : ");
    for (int i = 0; i < q->count; i++) {
        printf("%4d", vectorSeek(q->data, (q->head + i) % q->size));
    }
    printf("\n");
    return ;
}

int main() {
    srand(time(0));

    #define MAX_OP 10
    Queue *q = initQueue(5);
    for (int i = 0; i < MAX_OP; i++) {
        int op = rand() % 5, val = rand() % 100; 
        switch (op) {
            case 0:
                printf("front of queue : %d\n", front(q));
                pop(q);
                break;
            case 1:
            case 2:
            case 3:
            case 4: 
                printf("push %d to queue\n", val);
                push(q, val);
                break;
        }
        outputQueue(q);
    }
    clearQueue(q);
    return 0;
}

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

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

typedef struct LinkList{
    Node head, *tail;

}LinkList;

typedef struct Queue {
    LinkList *l;
    int count;
} Queue;

Node *getNewNode(int val) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->data = val;
    p->next = NULL;
    return p;
}

LinkList *initLinkList() {
    LinkList *l = (LinkList *)malloc(sizeof(LinkList));
    l->head.next = NULL;
    l->tail = &(l->head);
    return l;
}

int emptyList(LinkList *l) {
    return l->head.next == NULL;
}

int frontList(LinkList *l) {
    if (emptyList(l)) return 0;
    return l->head.next->data;
}

int insertTail(LinkList *l, int val) {
    Node *node = getNewNode(val);
    l->tail->next = node;
    l->tail = node;
    return 1;
}

int eraseHead(LinkList *l) {
    if (emptyList(l)) return 0;
    Node *p = l->head.next;
    l->head.next = l->head.next->next;
    free(p);
    if (p == l->tail) l->tail = &(l->head);
    return 1;
}

void clearLinkList(LinkList *l) {
    Node *p = l->head.next, *q;
    while (p) {
        q = p->next;
        free(p);
        p = q;
    }
    free(l);
    return ;
}

Queue *initQueue() {
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->l = initLinkList();
    q->count = 0;
    return q;
}

int empty(Queue *q) {
    return q->count == 0;
}

int front(Queue *q) {
    if (empty(q)) return 0;

    return frontList(q->l);
}

int pop(Queue *q) {
    eraseHead(q->l);
    q->count--;
    return 1;
}

int push(Queue *q, int val) {
    insertTail(q->l, val);
    q->count++;
    return 1;
}

void clearQueue(Queue *q) {
    if (q == NULL) return ;
    clearLinkList(q->l);
    free(q);
    return ;
}

void outputQueue(Queue *q) {
    printf("Queue : ");
    Node *p = q->l->head.next;
    for (int i = 0; i < q->count; i++) {
        printf("%4d", p->data);
        p = p->next;
    }
    printf("\n\n");
    return ;
}

int main() {
    srand(time(0));

    #define MAX_OP 10
    Queue *q = initQueue();
    for (int i = 0; i < MAX_OP; i++) {
        int op = rand() % 5, val = rand() % 100; 
        switch (op) {
            case 0:
                printf("front of queue : %d\n", front(q));
                pop(q);
                break;
            case 1:
            case 2:
            case 3:
            case 4: 
                printf("push %d to queue\n", val);
                push(q, val);
                break;
        }
        outputQueue(q);
    }
    clearQueue(q);

    return 0;
}

单调栈与单调队列

单调栈和单调队列是两种特殊的数据结构，广泛用于解决需要维护一定顺序或特性的算法问题。它们分别是栈和队列的变种，用于处理具有单调性的序列。以下是它们的定义、性质及应用场景。

单调栈

单调栈是一种栈结构，其元素保持单调性，通常分为单调递增栈和单调递减栈。

单调递增栈

定义：栈中的元素从栈底到栈顶是递增的，即栈顶元素最小。

性质：

当一个新元素入栈时，如果它小于或等于栈顶元素，则将栈顶元素弹出，直到栈为空或新元素大于栈顶元素为止，然后将新元素压入栈。
保证栈中的元素始终保持递增顺序。

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

typedef struct {
    int *data;
    int top;
    int capacity;
} MonotonicStack;

// 初始化单调递增栈
MonotonicStack* createStack(int capacity) {
    MonotonicStack *stack = (MonotonicStack *)malloc(sizeof(MonotonicStack));
    stack->data = (int *)malloc(capacity * sizeof(int));
    stack->top = -1;
    stack->capacity = capacity;
    return stack;
}

// 检查栈是否为空
int isEmpty(MonotonicStack *stack) {
    return stack->top == -1;
}

// 入栈操作
void push(MonotonicStack *stack, int value) {
    while (!isEmpty(stack) && stack->data[stack->top] >= value) {
        stack->top--;
    }
    stack->data[++stack->top] = value;
}

// 返回栈顶元素
int top(MonotonicStack *stack) {
    if (isEmpty(stack)) {
        return -1; // 栈为空
    }
    return stack->data[stack->top];
}

// 释放栈
void freeStack(MonotonicStack *stack) {
    free(stack->data);
    free(stack);
}

int main() {
    int arr[] = {3, 2, 1, 5, 6, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    MonotonicStack *stack = createStack(n);

    for (int i = 0; i < n; i++) {
        push(stack, arr[i]);
        printf("Top after pushing %d: %d\\n", arr[i], top(stack));
    }

    freeStack(stack);
    return 0;
}

单调递减栈

定义：栈中的元素从栈底到栈顶是递减的，即栈顶元素最大。
性质：
- 当一个新元素入栈时，如果它大于或等于栈顶元素，则将栈顶元素弹出，直到栈为空或新元素小于栈顶元素为止，然后将新元素压入栈。
- 保证栈中的元素始终保持递减顺序。

单调队列

单调队列是一种队列结构，其元素保持单调性，通常分为单调递增队列和单调递减队列。

单调递增队列

定义：队列中的元素从队头到队尾是递增的，即队尾元素最大。

性质：

当一个新元素入队时，如果它小于或等于队尾元素，则将队尾元素弹出，直到队列为空或新元素大于队尾元素为止，然后将新元素加入队尾。
保证队列中的元素始终保持递增顺序。

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

typedef struct {
    int *data;
    int front;
    int rear;
    int capacity;
} MonotonicQueue;

// 初始化单调递增队列
MonotonicQueue* createQueue(int capacity) {
    MonotonicQueue *queue = (MonotonicQueue *)malloc(sizeof(MonotonicQueue));
    queue->data = (int *)malloc(capacity * sizeof(int));
    queue->front = 0;
    queue->rear = 0;
    queue->capacity = capacity;
    return queue;
}

// 检查队列是否为空
int isEmpty(MonotonicQueue *queue) {
    return queue->front == queue->rear;
}

// 入队操作
void enqueue(MonotonicQueue *queue, int value) {
    while (!isEmpty(queue) && queue->data[(queue->rear - 1 + queue->capacity) % queue->capacity] >= value) {
        queue->rear = (queue->rear - 1 + queue->capacity) % queue->capacity;
    }
    queue->data[queue->rear] = value;
    queue->rear = (queue->rear + 1) % queue->capacity;
}

// 返回队头元素
int front(MonotonicQueue *queue) {
    if (isEmpty(queue)) {
        return -1; // 队列为空
    }
    return queue->data[queue->front];
}

// 释放队列
void freeQueue(MonotonicQueue *queue) {
    free(queue->data);
    free(queue);
}

int main() {
    int arr[] = {3, 2, 1, 5, 6, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    MonotonicQueue *queue = createQueue(n);

    for (int i = 0; i < n; i++) {
        enqueue(queue, arr[i]);
        printf("Front after enqueuing %d: %d\\n", arr[i], front(queue));
    }

    freeQueue(queue);
    return 0;
}