本文共 2091 字，大约阅读时间需要 6 分钟。

栗酱的数据结构题解

题目链接

数据结构题解

题意

栗酱在网上发现了一道有趣的数据结构题。题目描述了一个容器的操作，涉及七种不同的操作，需要模拟这些操作并输出结果。容器初始为空，操作包括从前面或后面插入、删除元素，以及头尾翻转、排序等功能。

操作说明

解题思路

该问题可以通过模拟容器的操作来实现。容器的操作涉及到头尾插入、删除以及整体翻转等操作。由于容器需要支持快速的插入、删除和翻转操作，可以选择使用双端队列（Deque）来模拟容器，因为双端队列支持O(1)时间复杂度的插入和删除操作。

具体步骤如下：

参考实现

#include 
   
    #include 
    
     using namespace std;int main() {    int n, m;    long long sum = 0;    cin >> n >> m;    int index;    deque
     
       dq;        for(int i = 0; i < m; i++) {        cin >> index;        if(index == 1) {            int tmp;            cin >> tmp;            dq.push_front(tmp);        } else if(index == 2) {            if(!dq.empty()) {                dq.pop_front();            }        } else if(index == 3) {            int tmp;            cin >> tmp;            dq.push_back(tmp);        } else if(index == 4) {            if(!dq.empty()) {                dq.pop_back();            }        } else if(index == 5) {            if(dq.size() <= 1) continue;            int left = dq.begin();            int right = dq.end();            int mid = dq.end() - (dq.size() / 2);            auto it = dq.begin();            while(it != mid) {                auto temp = *it;                *it = *mid;                mid--;                *mid = temp;                it++;            }        } else if(index == 6) {            cout << "Size: " << dq.size() << endl;            if(!dq.empty()) {                cout << "Elements: ";                for(auto num : dq) {                    cout << num << " ";                }                cout << endl;            }        } else if(index == 7) {            vector
      
        vec(dq.begin(), dq.end());            sort(vec.begin(), vec.end());            dq = deque(vec);        }    }    return 0;}
      
     
    
   

代码说明

• 使用双端队列（deque）来模拟容器，支持O(1)时间复杂度的插入和删除操作。
• 操作1和操作3分别从前面和后面插入元素。
• 操作2和操作4分别从前面和后面删除元素。
• 操作5实现头尾翻转，通过交换双端队列中相应位置的元素来实现。
• 操作6输出容器的大小和所有元素。
• 操作7将容器中的元素进行排序，使用内置的排序函数来实现。

转载地址：http://pyhlz.baihongyu.com/