1
- 连续内存, 随机访问 O(1)
2
- 插入/删除 O(n) (需要移动元素)
3
- 大小固定(静态数组)
4

5
int arr[10];          /* 栈上, 编译时确定大小 */
6
int *p = malloc(n * sizeof(int));  /* 堆上, 运行时确定 */

1
void reverse(int *arr, int n) {
2
    int left = 0, right = n - 1;
3
    while (left < right) {
4
        int tmp = arr[left];
5
        arr[left] = arr[right];
6
        arr[right] = tmp;
7
        left++;
8
        right--;
9
    }
10
}
11
/* 时间 O(n), 空间 O(1) */

1
/* 双指针法 */
2
void two_sum(int *arr, int n, int target) {
3
    int l = 0, r = n - 1;
4
    while (l < r) {
5
        int sum = arr[l] + arr[r];
6
        if (sum == target) {
7
            printf("(%d, %d)\n", arr[l], arr[r]);
8
            return;
9
        } else if (sum < target) {
10
            l++;
11
        } else {
12
            r--;
13
        }
14
    }
15
}
1 collapsed line
16
/* O(n) */

1
int removeDuplicates(int *arr, int n) {
2
    if (n <= 1) return n;
3
    int slow = 0;
4
    for (int fast = 1; fast < n; fast++) {
5
        if (arr[fast] != arr[slow]) {
6
            arr[++slow] = arr[fast];
7
        }
8
    }
9
    return slow + 1;  /* 新长度 */
10
}
11
/* 快慢指针, O(n) */

1
/* 字符串反转？ - 示例实现 */
2
void reverse_str(char *s) {
3
    int len = strlen(s);
4
    for (int i = 0, j = len - 1; i < j; i++, j--) {
5
        char tmp = s[i];
6
        s[i] = s[j];
7
        s[j] = tmp;
8
    }
9
}

1
/* 判断回文字符串？ - 示例实现 */
2
int is_palindrome(const char *s) {
3
    int l = 0, r = strlen(s) - 1;
4
    while (l < r) {
5
        if (s[l] != s[r]) return 0;
6
        l++;
7
        r--;
8
    }
9
    return 1;
10
}

1
/* strlen/strcpy/strcmp/strcat 自己实现？ - 示例实现 */
2
size_t my_strlen(const char *s) {
3
    const char *p = s;
4
    while (*p) p++;
5
    return p - s;
6
}
7

8
char *my_strcpy(char *dst, const char *src) {
9
    char *ret = dst;
10
    while ((*dst++ = *src++) != '\0');
11
    return ret;
12
}
13

14
int my_strcmp(const char *s1, const char *s2) {
15
    while (*s1 && *s1 == *s2) { s1++; s2++; }
2 collapsed lines
16
    return *(unsigned char *)s1 - *(unsigned char *)s2;
17
}

1
/* memcpy: 不处理内存重叠, 速度快 */
2
/* memmove: 处理内存重叠(可能从后往前拷贝) */
3
void *my_memmove(void *dst, const void *src, size_t n) {
4
    char *d = dst;
5
    const char *s = src;
6
    if (d < s) {
7
        while (n--) *d++ = *s++;       /* 从前往后 */
8
    } else {
9
        d += n; s += n;
10
        while (n--) *--d = *--s;       /* 从后往前 */
11
    }
12
    return dst;
13
}

1
void rotate(int *arr, int n, int k) {
2
    k %= n;
3
    reverse(arr, 0, n - 1);     /* 全部反转 */
4
    reverse(arr, 0, k - 1);     /* 前k个反转 */
5
    reverse(arr, k, n - 1);     /* 后面反转 */
6
}

1
int majorityElement(int *arr, int n) {
2
    int candidate = arr[0], count = 1;
3
    for (int i = 1; i < n; i++) {
4
        if (count == 0) { candidate = arr[i]; count = 1; }
5
        else if (arr[i] == candidate) count++;
6
        else count--;
7
    }
8
    return candidate;  /* 题目保证一定存在 */
9
}

1
void merge(int *a, int m, int *b, int n) {
2
    int i = m - 1, j = n - 1, k = m + n - 1;
3
    while (i >= 0 && j >= 0) {
4
        a[k--] = (a[i] > b[j]) ? a[i--] : b[j--];
5
    }
6
    while (j >= 0) a[k--] = b[j--];  /* b 有剩余 */
7
    /* a 有剩余不用处理，已经在原位 */
8
}

1
void build_next(const char *pat, int *next, int n) {
2
    next[0] = 0;
3
    int len = 0, i = 1;
4
    while (i < n) {
5
        if (pat[i] == pat[len]) { next[i++] = ++len; }
6
        else if (len > 0) { len = next[len - 1]; }
7
        else { next[i++] = 0; }
8
    }
9
}
10

11
int kmp_search(const char *text, const char *pat) {
12
    int m = strlen(text), n = strlen(pat);
13
    int next[n];
14
    build_next(pat, next, n);
15
    int i = 0, j = 0;
8 collapsed lines
16
    while (i < m) {
17
        if (text[i] == pat[j]) { i++; j++; }
18
        else if (j > 0) { j = next[j - 1]; }
19
        else { i++; }
20
        if (j == n) return i - n;  /* 找到 */
21
    }
22
    return -1;
23
}

1
int my_atoi(const char *s) {
2
    while (*s == ' ') s++;            /* 跳空格 */
3
    int sign = 1;
4
    if (*s == '-' || *s == '+') { sign = (*s == '-') ? -1 : 1; s++; }
5
    long result = 0;
6
    while (*s >= '0' && *s <= '9') {
7
        result = result * 10 + (*s - '0');
8
        if (result * sign > INT_MAX) return INT_MAX;
9
        if (result * sign < INT_MIN) return INT_MIN;
10
        s++;
11
    }
12
    return (int)(result * sign);
13
}

1
char *addStrings(const char *a, const char *b) {
2
    int i = strlen(a) - 1, j = strlen(b) - 1;
3
    int carry = 0, k = 0;
4
    char result[1024];
5
    while (i >= 0 || j >= 0 || carry) {
6
        int sum = carry;
7
        if (i >= 0) sum += a[i--] - '0';
8
        if (j >= 0) sum += b[j--] - '0';
9
        result[k++] = sum % 10 + '0';
10
        carry = sum / 10;
11
    }
12
    result[k] = '\0';
13
    /* 反转 result */
14
    for (int l = 0, r = k - 1; l < r; l++, r--) {
15
        char t = result[l]; result[l] = result[r]; result[r] = t;
3 collapsed lines
16
    }
17
    return strdup(result);
18
}

1
int lengthOfLongestSubstring(const char *s) {
2
    int count[128] = {0};   /* ASCII 字符计数 */
3
    int left = 0, max_len = 0;
4
    for (int right = 0; s[right]; right++) {
5
        count[(int)s[right]]++;
6
        while (count[(int)s[right]] > 1) {
7
            count[(int)s[left]]--;
8
            left++;
9
        }
10
        int len = right - left + 1;
11
        if (len > max_len) max_len = len;
12
    }
13
    return max_len;
14
}

1
void spiralOrder(int mat[][N], int rows, int cols) {
2
    int top = 0, bot = rows - 1, left = 0, right = cols - 1;
3
    while (top <= bot && left <= right) {
4
        for (int j = left; j <= right; j++) printf("%d ", mat[top][j]);
5
        top++;                                  // 入栈
6
        for (int i = top; i <= bot; i++) printf("%d ", mat[i][right]);
7
        right--;
8
        if (top <= bot) {
9
            for (int j = right; j >= left; j--) printf("%d ", mat[bot][j]);
10
            bot--;
11
        }
12
        if (left <= right) {
13
            for (int i = bot; i >= top; i--) printf("%d ", mat[i][left]);
14
            left++;
15
        }
2 collapsed lines
16
    }
17
}

1
int searchMatrix(int mat[][N], int rows, int cols, int target) {
2
    int i = 0, j = cols - 1;  /* 右上角出发 */
3
    while (i < rows && j >= 0) {
4
        if (mat[i][j] == target) return 1;
5
        else if (mat[i][j] > target) j--;
6
        else i++;
7
    }
8
    return 0;
9
}

1
/* 字符串转整数(atoi) — 处理边界情况 */
2
int myAtoi(const char *s) {
3
    while (*s == ' ') s++;             // 1. 跳过前导空格
4
    int sign = 1;
5
    if (*s == '-' || *s == '+')        // 2. 处理正负号
6
        sign = (*s++ == '-') ? -1 : 1;
7
    long result = 0;
8
    while (*s >= '0' && *s <= '9') {   // 3. 逐位转换
9
        result = result * 10 + (*s++ - '0');
10
        if (result * sign > INT_MAX) return INT_MAX;  // 4. 溢出检查
11
        if (result * sign < INT_MIN) return INT_MIN;
12
    }
13
    return (int)(result * sign);
14
}
15
/* 关键边界: 溢出/空串/非数字字符/正负号/前导空格 */

1
int partition(int *arr, int lo, int hi) {
2
    int pivot = arr[hi], i = lo;                // 基准元素(快排)
3
    for (int j = lo; j < hi; j++) {
4
        if (arr[j] >= pivot) {  /* 降序partition, 大的在前 */
5
            int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
6
            i++;
7
        }
8
    }
9
    int t = arr[i]; arr[i] = arr[hi]; arr[hi] = t;
10
    return i;
11
}
12

13
int findKthLargest(int *arr, int n, int k) {
14
    int lo = 0, hi = n - 1;
15
    while (lo <= hi) {
7 collapsed lines
16
        int p = partition(arr, lo, hi);
17
        if (p == k - 1) return arr[p];
18
        else if (p < k - 1) lo = p + 1;
19
        else hi = p - 1;
20
    }
21
    return -1;
22
}

1
int maxSubArray(int *arr, int n) {
2
    int current_sum = arr[0], max_sum = arr[0];
3
    for (int i = 1; i < n; i++) {
4
        /* 要么接上前面, 要么自己重新开始 */
5
        current_sum = (current_sum + arr[i] > arr[i]) ?
6
                       current_sum + arr[i] : arr[i];
7
        if (current_sum > max_sum) max_sum = current_sum;
8
    }
9
    return max_sum;
10
}

1
typedef struct ListNode {
2
    int val;
3
    struct ListNode *next;
4
} ListNode;
5

6
/* 创建节点 */
7
ListNode *new_node(int val) {
8
    ListNode *node = (ListNode *)malloc(sizeof(ListNode));               // 动态分配节点
9
    node->val = val;
10
    node->next = NULL;                          // 修改指针指向
11
    return node;
12
}
13

14
/* 头插法建链表 */
15
ListNode *head = NULL;
5 collapsed lines
16
for (int i = 0; i < n; i++) {
17
    ListNode *node = new_node(data[i]);
18
    node->next = head;                          // 修改指针指向
19
    head = node;
20
}

1
ListNode *reverse(ListNode *head) {
2
    ListNode *prev = NULL, *curr = head;
3
    while (curr) {
4
        ListNode *next = curr->next;
5
        curr->next = prev;                          // 修改指针指向
6
        prev = curr;
7
        curr = next;
8
    }
9
    return prev;
10
}
11

12
/* 递归版 */
13
ListNode *reverse_rec(ListNode *head) {
14
    if (!head || !head->next) return head;                // 头节点的下一个
15
    ListNode *new_head = reverse_rec(head->next);                            // 头节点的下一个
5 collapsed lines
16
    head->next->next = head;                          // 修改指针指向
17
    head->next = NULL;                          // 修改指针指向
18
    return new_head;
19
}
20
/* 时间 O(n), 空间 O(1) / O(n) */

1
/* 快慢指针(Floyd 判环法) */
2
int hasCycle(ListNode *head) {
3
    ListNode *slow = head, *fast = head;
4
    while (fast && fast->next) {
5
        slow = slow->next;
6
        fast = fast->next->next;
7
        if (slow == fast) return 1;  /* 有环 */
8
    }
9
    return 0;
10
}
11

12
/* 找环入口点: 相遇后, 一个从 head 出发, 一个从相遇点出发, 再次相遇即入口 */
13
ListNode *detectCycle(ListNode *head) {
14
    ListNode *slow = head, *fast = head;
15
    while (fast && fast->next) {
13 collapsed lines
16
        slow = slow->next;
17
        fast = fast->next->next;
18
        if (slow == fast) {
19
            ListNode *p = head;
20
            while (p != slow) {
21
                p = p->next;
22
                slow = slow->next;
23
            }
24
            return p;  /* 环入口 */
25
        }
26
    }
27
    return NULL;
28
}

1
ListNode *merge(ListNode *l1, ListNode *l2) {
2
    ListNode dummy = {0, NULL};
3
    ListNode *tail = &dummy;
4
    while (l1 && l2) {
5
        if (l1->val <= l2->val) {
6
            tail->next = l1; l1 = l1->next;             // 修改指针指向
7
        } else {
8
            tail->next = l2; l2 = l2->next;             // 修改指针指向
9
        }
10
        tail = tail->next;
11
    }
12
    tail->next = l1 ? l1 : l2;                  // 修改指针指向
13
    return dummy.next;
14
}

1
ListNode *removeNthFromEnd(ListNode *head, int n) {
2
    ListNode dummy = {0, head};
3
    ListNode *fast = &dummy, *slow = &dummy;
4
    /* fast 先走 n+1 步 */
5
    for (int i = 0; i <= n; i++) fast = fast->next;
6
    /* 同步走到 fast == NULL */
7
    while (fast) {
8
        fast = fast->next;
9
        slow = slow->next;
10
    }
11
    ListNode *del = slow->next;
12
    slow->next = del->next;                     // 修改指针指向
13
    free(del);
14
    return dummy.next;
15
}

1
ListNode *middleNode(ListNode *head) {
2
    ListNode *slow = head, *fast = head;
3
    while (fast && fast->next) {
4
        slow = slow->next;
5
        fast = fast->next->next;
6
    }
7
    return slow;  /* 偶数个节点时返回第二个中间 */
8
}

1
ListNode *getIntersection(ListNode *headA, ListNode *headB) {
2
    ListNode *pA = headA, *pB = headB;
3
    while (pA != pB) {
4
        pA = pA ? pA->next : headB;
5
        pB = pB ? pB->next : headA;
6
    }
7
    return pA;  /* NULL = 不相交, 非 NULL = 交点 */
8
}
9
/* 原理: 两指针走完自己的链表后走对方的, 走过的总距离相等 */

1
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
2
    ListNode dummy = {0, NULL};
3
    ListNode *tail = &dummy;
4
    int carry = 0;
5
    while (l1 || l2 || carry) {
6
        int sum = carry;
7
        if (l1) { sum += l1->val; l1 = l1->next; }
8
        if (l2) { sum += l2->val; l2 = l2->next; }
9
        tail->next = new_node(sum % 10);            // 修改指针指向
10
        tail = tail->next;
11
        carry = sum / 10;
12
    }
13
    return dummy.next;
14
}

1
int isPalindrome(ListNode *head) {
2
    ListNode *slow = head, *fast = head;
3
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
4
    /* slow 指向后半段起点 */
5
    ListNode *rev = reverse(slow);  /* 反转后半段 */
6
    ListNode *p = head, *q = rev;
7
    int result = 1;
8
    while (q) {
9
        if (p->val != q->val) { result = 0; break; }
10
        p = p->next; q = q->next;
11
    }
12
    reverse(rev);  /* 恢复原链表 */
13
    return result;
14
}

1
ListNode *sortList(ListNode *head) {
2
    if (!head || !head->next) return head;                // 头节点的下一个
3
    /* 快慢指针找中点(慢指针前一个位置) */
4
    ListNode *slow = head, *fast = head->next;                             // 头节点的下一个
5
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
6
    ListNode *mid = slow->next;
7
    slow->next = NULL;  /* 断开 */
8
    ListNode *left = sortList(head);
9
    ListNode *right = sortList(mid);
10
    return merge(left, right);  /* 合并两个有序链表(Q24) */
11
}

1
ListNode *reverseKGroup(ListNode *head, int k) {
2
    ListNode dummy = {0, head};
3
    ListNode *prev_group = &dummy;
4
    while (1) {
5
        ListNode *kth = prev_group;
6
        for (int i = 0; i < k; i++) {
7
            kth = kth->next;
8
            if (!kth) return dummy.next;  /* 不足k个 */
9
        }
10
        ListNode *next_group = kth->next;
11
        ListNode *curr = prev_group->next, *prev = next_group;
12
        for (int i = 0; i < k; i++) {
13
            ListNode *tmp = curr->next;
14
            curr->next = prev;                          // 修改指针指向
15
            prev = curr;
7 collapsed lines
16
            curr = tmp;
17
        }
18
        ListNode *tmp = prev_group->next;  /* 原来的第一个=翻转后的最后一个 */
19
        prev_group->next = prev;           /* 接上翻转后的头 */
20
        prev_group = tmp;
21
    }
22
}

1
/* 核心操作: */
2
/* get(key): hash找到节点 → 移到头部 → 返回值 */
3
/* put(key,val): hash找到 → 更新+移到头部; 没找到 → 新建插头部, 满了删尾 */
4
/* 双向链表保证 移动/删除/插入 都是 O(1) */

1
/* 复制带随机指针的链表(LeetCode 138) */
2
typedef struct Node { int val; struct Node *next, *random; } Node;
3

4
/* 方法: 交错插入法 O(n)时间 O(1)空间 */
5
Node* copyRandomList(Node* head) {
6
    if (!head) return NULL;
7
    // 1. 在每个节点后插入副本: A→A'→B→B'→C→C'
8
    for (Node *cur = head; cur; cur = cur->next->next) {
9
        Node *copy = (Node*)malloc(sizeof(Node));                   // 动态分配节点
10
        copy->val = cur->val;
11
        copy->next = cur->next;                     // 修改指针指向
12
        cur->next = copy;                          // 修改指针指向
13
    }
14
    // 2. 设置random: A'.random = A.random.next
15
    for (Node *cur = head; cur; cur = cur->next->next)
10 collapsed lines
16
        cur->next->random = cur->random ? cur->random->next : NULL;
17
    // 3. 拆分两个链表
18
    Node *new_head = head->next;                             // 头节点的下一个
19
    for (Node *cur = head; cur; cur = cur->next) {
20
        Node *copy = cur->next;
21
        cur->next = copy->next;                    // 修改指针指向
22
        copy->next = copy->next ? copy->next->next : NULL; // 修改指针指向
23
    }
24
    return new_head;
25
}

1
/* 在 node 之后插入 new_node */
2
void insert_after(ListNode2 *node, ListNode2 *new_node) {
3
    new_node->next = node->next;                    // 修改指针指向
4
    new_node->prev = node;
5
    if (node->next) node->next->prev = new_node;
6
    node->next = new_node;                      // 修改指针指向
7
}
8
/* 删除 node(已知位置) */
9
void delete_node(ListNode2 *node) {
10
    if (node->prev) node->prev->next = node->next;                    // 修改指针指向
11
    if (node->next) node->next->prev = node->prev;
12
    free(node);
13
}

1
int josephus(int n, int m) {
2
    int result = 0;  /* f(1) = 0 */
3
    for (int i = 2; i <= n; i++) {
4
        result = (result + m) % i;
5
    }
6
    return result + 1;  /* 转为1-based编号 */
7
}

1
Level 3: 1 ───────────────→ 9 ───→ nil
2
Level 2: 1 ───→ 4 ────────→ 9 ───→ nil
3
Level 1: 1 → 3 → 4 → 5 → 7 → 9 → nil

1
void remove_duplicates(Node *head) {
2
    Node *curr = head;
3
    while (curr && curr->next) {
4
        if (curr->val == curr->next->val) {
5
            Node *dup = curr->next;
6
            curr->next = dup->next;                     // 修改指针指向
7
            free(dup);
8
        } else {
9
            curr = curr->next;
10
        }
11
    }
12
}
13
/* [1,1,2,3,3] → [1,2,3] */

1
void remove_dup_unsorted(Node *head) {
2
    int seen[10000] = {0};  /* 简单用数组做哈希 */
3
    Node *prev = NULL, *curr = head;
4
    while (curr) {
5
        if (seen[curr->val]) {
6
            prev->next = curr->next;                    // 修改指针指向
7
            free(curr);
8
            curr = prev->next;
9
        } else {
10
            seen[curr->val] = 1;
11
            prev = curr;
12
            curr = curr->next;
13
        }
14
    }
15
}

1
Node *partition(Node *head, int x) {
2
    Node less_head = {0}, greater_head = {0};
3
    Node *less = &less_head, *greater = &greater_head;
4
    while (head) {
5
        if (head->val < x) { less->next = head; less = less->next; }     // 修改指针指向
6
        else { greater->next = head; greater = greater->next; } // 修改指针指向
7
        head = head->next;                             // 头节点的下一个
8
    }
9
    greater->next = NULL;                          // 修改指针指向
10
    less->next = greater_head.next;             // 修改指针指向
11
    return less_head.next;
12
}

1
/* AVL 右旋 */
2
Node* rightRotate(Node* y) {
3
    Node* x = y->left;
4
    y->left = x->right;                      // 指向左子树
5
    x->right = y;                            // 指向右子树
6
    y->height = 1 + max(height(y->left), height(y->right));
7
    x->height = 1 + max(height(x->left), height(x->right));
8
    return x;
9
}

1
/* BFS 模板 */
2
queue<int> q;
3
q.push(start); visited[start] = true;                  // 访问标记数组
4
while (!q.empty()) {
5
    int u = q.front(); q.pop();                       // 队头指针
6
    for (int v : adj[u])
7
        if (!visited[v]) { visited[v] = true; q.push(v); }         // 访问标记数组
8
}

1
/* 数组实现 */
2
#define MAX_SIZE 100
3
typedef struct {  // 结构体定义
4
    int data[MAX_SIZE];
5
    int top;
6
} Stack;
7

8
void stack_init(Stack *s) { s->top = -1; }
9
int stack_empty(Stack *s) { return s->top == -1; }
10
int stack_full(Stack *s) { return s->top == MAX_SIZE - 1; }
11

12
void stack_push(Stack *s, int val) {
13
    if (!stack_full(s))
14
        s->data[++s->top] = val;
15
}
10 collapsed lines
16
int stack_pop(Stack *s) {
17
    if (!stack_empty(s))
18
        return s->data[s->top--];                                 // 出栈
19
    return -1;
20
}
21
int stack_peek(Stack *s) {
22
    if (!stack_empty(s))
23
        return s->data[s->top];
24
    return -1;
25
}

1
/* 队列的实现(环形数组)？ - 示例实现 */
2
#define QSIZE 100
3
typedef struct {  // 结构体定义
4
    int data[QSIZE];
5
    int head, tail, count;
6
} Queue;
7

8
void queue_init(Queue *q) { q->head = q->tail = q->count = 0; }
9
int queue_empty(Queue *q) { return q->count == 0; }
10
int queue_full(Queue *q) { return q->count == QSIZE; }
11

12
void enqueue(Queue *q, int val) {
13
    if (!queue_full(q)) {
14
        q->data[q->tail] = val;
15
        q->tail = (q->tail + 1) % QSIZE;
12 collapsed lines
16
        q->count++;
17
    }
18
}
19
int dequeue(Queue *q) {
20
    if (!queue_empty(q)) {
21
        int val = q->data[q->head];
22
        q->head = (q->head + 1) % QSIZE;
23
        q->count--;
24
        return val;
25
    }
26
    return -1;
27
}

1
/* 有效括号匹配？ - 示例实现 */
2
int isValid(const char *s) {
3
    Stack st;
4
    stack_init(&st);
5
    while (*s) {
6
        if (*s == '(' || *s == '[' || *s == '{') {
7
            stack_push(&st, *s);
8
        } else {
9
            if (stack_empty(&st)) return 0;
10
            char top = stack_pop(&st);
11
            if ((*s == ')' && top != '(') ||
12
                (*s == ']' && top != '[') ||
13
                (*s == '}' && top != '{'))
14
                return 0;
15
        }
4 collapsed lines
16
        s++;
17
    }
18
    return stack_empty(&st);
19
}

1
typedef struct {
2
    Stack in_stack;   // 入队用
3
    Stack out_stack;  // 出队用
4
} MyQueue;
5

6
void queue_push(MyQueue *q, int val) {
7
    stack_push(&q->in_stack, val);
8
}
9

10
int queue_pop(MyQueue *q) {
11
    if (stack_empty(&q->out_stack)) {
12
        // out_stack空时,把in_stack全部倒过来
13
        while (!stack_empty(&q->in_stack)) {
14
            stack_push(&q->out_stack, stack_pop(&q->in_stack));
15
        }
4 collapsed lines
16
    }
17
    return stack_pop(&q->out_stack);
18
}
19
// 均摊时间复杂度: O(1)