红魔咖啡馆


头发越掉越多，头发越掉越少

【数据结构】栈

  • ~4.08K 字
  1. 1. 栈
    1. 1.1. 特点
    2. 1.2. 顺序表实现
      1. 1.2.1. 初始化
      2. 1.2.2. 判断空栈
      3. 1.2.3. 压栈
      4. 1.2.4. 出栈
      5. 1.2.5. 获取栈顶元素
      6. 1.2.6. 动态分配内存
    3. 1.3. 链表实现
      1. 1.3.1. 初始化
      2. 1.3.2. 判空
      3. 1.3.3. 压栈
      4. 1.3.4. 出栈
      5. 1.3.5. 获取栈顶元素
    4. 1.4. 单调栈
      1. 1.4.1. 无重复值
      2. 1.4.2. 有重复值
      3. 1.4.3. 模板

栈

特点

  • 仅可在表尾操作
  • 表尾称为栈顶(top)，表头称为栈底
  • 不含元素的空表为空栈
  • 栈遵循后进先出（LIFO）的原则
  • 基本操作包括push，pop

顺序表实现

初始化

1
2
3
4
5
6
7
8
9
typedef struct{
  ElemType data[MAXSIZE];
  int top;
}Stack;

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

判断空栈

1
2
3
4
5
6
7
8
9
int isEmpty(Stack *s){
  if (s->top==-1){
    printf("Empty");
    return 1;
  }
  else {
    return 0;
  }
}

压栈

1
2
3
4
5
6
7
8
9
10
// 压栈
int push(Stack *s, ElemType e){
  if (s->top>=MAXSIZE-1){
    printf("Full");
    return 0;
  }
  s->top++; // 栈顶上移一位
  s->data[s->top]= e; // 压入数据
  return 1;
}

出栈

1
2
3
4
5
6
7
8
9
10
// 出栈
int pop(Stack *s, ElemType *e){
  if (s->top==-1){
    printf("Empty");
    return 0;
  }
  *e = s->data[s->top]; // 弹出栈顶元素
  s->top--; // 栈顶下移一位
  return 1;
}

获取栈顶元素

1
2
3
4
5
6
7
8
9
// 获取栈顶元素
int getTop(Stack *s, ElemType *e){
  if (s->top==-1){
    printf("Empty");
    return 0;
  }
  *e = s->data[s->top];
  return 1;
}

动态分配内存

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct{
  ElemType *data;
  int top;
}Stack;

// 栈的初始化
Stack* initStack(){;
  Stack *s = (Stack*)malloc(sizeof(Stack));
  s->data = (ElemType*)malloc(sizeof(ElemType)*MAXSIZE);
  s->top = -1; // 表示空栈
  return s;
}

链表实现

使用单向链表来实现栈

尾节点为栈底，首节点为栈顶

  • 压栈：链表头插法
  • 出栈：删除头节点后的首节点
  • 判空：只有头节点（head->next == NULL）
  • 获取栈顶数据：找头节点的next的data（head->next->data）

初始化

1
2
3
4
5
typedef int ElemType;
typedef struct stack{
  ElemType data;
  struct stack *next;
}Stack;

判空

1
2
3
4
5
6
7
8
9
10
// 判空
int isEmpty(Stack *s){
  if (s->next == NULL){ // 头节点的next指向NULL
    printf("Empty");
    return 1;
  }
  else {
    return 0;
  }
}

压栈

1
2
3
4
5
6
7
8
9
// 压栈
int push(Stack *s, ElemType e){
  Stack* p = (Stack*)malloc(sizeof(Stack));
  p->data = e;
  p->next = s->next;
  s->next = p;
  return 1;

}

出栈

1
2
3
4
5
6
7
8
9
10
11
12
// 出栈
int pop(Stack *s, ElemType *e){
  if (s->next==NULL){
    printf("Empty");
    return 0;
  }
  Stack *q = s->next;
  *e = q->data;
  s->next = q->next;
  free(q);
  return 1;
}

获取栈顶元素

1
2
3
4
5
6
7
8
9
// 获取栈顶元素
int getTop(Stack *s,ElemType *e){
  if (s->next == NULL){
    printf("Empty");
    return 0;
  }
  *e = s->next->data;
  return 1;
}

单调栈

单调栈常用于寻找元素：

  • 寻找元素的下一个更大/更小元素
  • 寻找元素左侧第一个更大/更小元素

进一步，单调栈可以应用于优化DP等问题

无重复值

对给定数组(如[2, 5, 6, 7, 3, 4, 1, 8])，寻找每个位置的左边与右边离自己最近比自己小的位置在哪

暴力遍历会有的时间复杂度，我们可以用栈来优化

创建一个空栈（存下标），该栈要求大压小：

没东西直接放入对应下标

若满足大压小则放入，当不满足时弹出栈顶

此时弹出后的栈顶就是弹出元素左边最近且比它小的数

使得该元素弹出的元素就是弹出元素右边最近且比它小的数

如依次放入2, 5, 6, 7，当压入3时，发现元素小于栈顶元素，故无法压入

此时弹出栈顶元素7，则7左边最近且比它小的数为6，右边最近且比它小的数3

继续压入3，发现元素小于栈顶元素，无法压入

此时弹出栈顶元素6，则6左边最近且比它小的数为5，右边最近且比它小的数为3

……

直到可以压入时再压入，继续往后压入元素下标

遍历结束，开始清算栈中剩下的数字

若此时没有数字让当前位置弹出，则右边最近且比它小的数不存在

若此时底下已经没有元素压着了，则左边最近且比它小的数不存在

同理，使用小压大的单调栈可以寻找离自己最近比自己大的位置

有重复值

对给定数组(如[2, 3, 4, 3, 2, 1, 3, 5, 6, 3, 4, 3, 2])，寻找每个位置的左边与右边离自己最近比自己小的位置在哪

创建一个大压小的空栈

整体逻辑与无重复值相同，但当压入下一个数时发现与当前数相同时

不压入该数，而是弹出当前值，作为当前数右侧离自己最近比自己小的值（此时是错误的）

当遍历阶段与清算阶段结束后，各个元素关系如下，其中框住的是错误的位置

左侧无需修正，右侧倒序遍历每个位置的右侧元素，若发现与遍历元素相等，则将右侧元素对应的右侧离它最近比它小的元素作为当前遍历元素的右侧元素

如发现9位置为3，而其右侧元素为11位置的3，则我们看11位置的3的右侧元素，是12位置的2，那我们将9位置右侧元素改为12位置的2

我们可以发现，需要此种操作时，两数之间总会有大于两数的数

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
//#include <stack>
using namespace std;
const int N = 3e6+10;
//stack<int> st;
int arr[N];
int stack[N]; // 数组实现栈, 内部存的是下标
int ans[N][2]; // 二维的0位置为左侧答案，1位置为右侧答案
int n, r;

int main(){
  cin >> n;
  for (int i = 0;i<n;i++) cin >> arr[i];
  r = 0;
  int cur;
  // 遍历阶段
  for (int i = 0;i<n;i++){
    while(r>0 && arr[stack[r-1]]<=arr[i]){ // 小于等于时看大于当前位置，大于等于反之
      cur = stack[--r]; // 当前弹出位置
      ans[cur][0] = r>0 ? stack[r-1]:-1; // 左侧最近答案
      ans[cur][1] = i; // 右侧最近答案
    }
    stack[r++]=i;
  }
  // 清算阶段
   while (r>0){
    cur = stack[--r];
    ans[cur][0] = r>0? stack[r-1]:-1;
    ans[cur][1] = -1;
   }
   // 修正阶段
   // 只需要修正右侧答案，从右往左修正，n-1右侧的一定是-1，不需要修正
   for(int i = n-2; i>=0; i--){
    if(ans[i][1]!=-1 && arr[ans[i][1]]==arr[i]){
      ans[i][1] = ans[ans[i][1]][1]; // 现在右侧答案的右侧的答案作为现在右侧的答案
    }
   }

   for (int i = 0;i<n;i++){
     cout <<ans[i][0]+1<<' '<<ans[i][1]+1<<endl;
   }
}

根据具体题目，若只让求右侧等条件，相等时也可以进栈

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
赞助喵
非常感谢您的喜欢！
赞助喵