---
title: "栈"
created: 2025-11-28
tags:
  - 算法
---

# 栈

## 题目 [栈](https://www.acwing.com/problem/content/4976/)

![[image-94819443.png]]

## 思路分析

对于出现过的数 删除 再插入在头

对于没出现过的数 插入在头

所以可以直接用双链表模拟 很方便的进行插入和删除操作

用一个哈希表存放每个结点的位置 如果该结点出现过了 我们可以很容易查到要删哪个点

或者反向思考

从最后一个字符串往回看

![[反推-b0f944f0.gif]]

从下往上看 如果没出现过 直接输出 并放入map中

如果出现过 就跳过 看下一个

## 代码实现

**正向模拟**

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N = 200010, M = 11;

int n;

int l[N], r[N], idx;

char str[N][M];

unordered_map<string, int> pos;

int insert(int k, int x)

{

    l[x] = k, r[x] = r[k];

    l[r[x]] = x, r[k] = x;

}

void remove(int k)

{

    l[r[k]] = l[k];

    r[l[k]] = r[k];

}

int main()

{

    l[0] = r[0] = 1;

    l[1] = r[1] = 0;

    idx = 2;

    scanf("%d", &n);

    for (int i = 0; i < n; i ++ )

    {

        char* s = str[idx];

        scanf("%s", s);

        if (pos.count(s))

        {

            int k = pos[s];

            remove(k);

            insert(0, k);

        }

        else

        {

            pos[s] = idx;

            insert(0, idx);

            idx ++ ;

        }

    }

    for (int i = r[0]; i != 1; i = r[i])

        puts(str[i]);

    return 0;

}
```

**反向推导**

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N = 200010, M = 11;

int n;

char str[N][M];

int main()

{

    scanf("%d", &n);

    for (int i = 0; i < n; i ++ )

        scanf("%s", str[i]);

    unordered_set<string> hash;

    for (int i = n - 1; i >= 0; i -- )

        if (!hash.count(str[i]))

        {

            puts(str[i]);

            hash.insert(str[i]);

        }

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[春晚刘谦魔术 约瑟夫问题|春晚刘谦魔术 约瑟夫问题]] 🏠 [[00-刷题理模型]] ➡️ [[消除游戏|消除游戏]]