题解 | #双端队列设计#

#include <ios>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param operations int整型vector<vector<>>
     * @param k int整型
     * @return int整型vector
     */
    vector<int> performOperations(vector<vector<int> >& operations, int k) {
        // write code here
        int n = operations.size();
        vector<int> res;
        DoubleQue que(k);
        for (int i = 0; i < n; ++i) {
            switch (operations[i][0]) {
                case 1:
                    res.push_back(que.insertFront(operations[i][1]));
                    break;
                case 2:
                    res.push_back(que.insertRear(operations[i][1]));
                    break;
                case 3:
                    res.push_back(que.deleteFront());
                    break;
                case 4:
                    res.push_back(que.deleteRear());
                    break;
                case 5:
                    res.push_back(que.getFront());
                    break;
                case 6:
                    res.push_back(que.getRear());
                    break;
            }
        }
        return res;

    }


    class DoubleQue {
      private:
        vector<int> vals;
        int _capacity;
        int _size;
        int _head, _tail;
      public:
        DoubleQue(int k ): _capacity(k), _size(0), vals(vector<int>(k)), _head(0),
            _tail(0) {}

        bool isFull() const {
            return _size == _capacity;
        }

        bool isEmpty() const {
            return _size == 0;
        }

        int getFront() const {
            if (_size == 0)
                return -1;
            return vals[_head];
        }

        int getRear() const {
            if (_size == 0)
                return -1;
            return vals[(_tail-1+_capacity)%_capacity];
        }

        int deleteFront() {
            if (_size == 0)
                return -1;
            --_size;
            _head = (_head + 1) % _capacity;
            return 0;
        }

        int deleteRear() {
            if (_size == 0)
                return -1;
            --_size;
            _tail = (_tail - 1 + _capacity) % _capacity;
            return 0;
        }

        int insertFront(int value) {
            if (_capacity == _size)
                return -1;
            ++_size;
            _head = (_head - 1 + _capacity) % _capacity;
            vals[_head] = value;
            return 0;
        }

        int insertRear(int value) {
            if (_capacity == _size)
                return -1;
            ++_size;
            vals[_tail] = value;
            _tail = (_tail + 1) % _capacity;
            return 0;
        }

    };

};