跳转至

双端队列

两端都能进或出

数组版-双端队列

规定 \(q[0]\) 是左指针，\(q[1]\) 是右指针，并且左右指针都能往左或者往右移动

双端队列示意图

双端队列示意图

init 初始化

我们规定，数组下标为 \(q[0]\)、\(q[1]\) 的数据域不能存放数据，即 \(q[q[0]]\) 和 \(q[q[1]]\) 不能放数据， 初始化时，\(q[0] = 2, q[1] = 3\)

双端队列-不能放数据的两个下标

sddl不能放数据

双端队列-初始状态图片

队列初始状态

void init(int q[])
{
    q[0] = 2, q[1] = 3;
}

ml 左边元素下标

  • 如果 pos != 2 ，则 ml = pos - 1
  • 否则 ml = N - 1

若 \(i\) 是区间 \([0, N - 3]\) 的元素，左移就相当于是 \(i - 1\) 对 \(N - 2\) 同余操作，即 \((i - 1) \bmod (N - 2)\)

已知 \(pos\) 是区间 \([2, N - 1]\) 的元素，也是 \([0, N - 3] + 2\) 的元素，\(pos\) 左移就相当于是 \((pos - 2 - 1) \bmod (N - 2) + 2 = (pos - 2 - 1 + N - 2) \bmod (N - 2) + 2\)

int ml(int pos)
{
    return (pos - 5 + N) % (N - 2) + 2;
}

mr 右边元素的下标

  • 如果 pos != N-1 ，则 mr = pos + 1
  • 否则 ml = 2

已知 \(pos\) 的取值范围：\([2, N-1]\) ，在该区间内右移，就相当于在区间 \([0, N - 3]\) 内右移，需要先 \(pos - 2\) 化成区间 \([0, N - 3]\) 内的元素，再对右移操作 \((pos - 2 + 1) \bmod ( N - 2)\) 同余

int mr(int pos)
{
    return (pos - 1) % (N - 2) + 2;
}

empty

只要 \(q[0]\) 紧跟在 \(q[1]\) 的左手边，就说明双端队列为空

双端队列空状态图例

双端队列空状态

bool empty(int q[])
{
    return ml(q[1]) == q[0];
}

size

如果 \(q[1] > q[0]\)，\(size = q[1] - q[0] - 1\)；

如果 \(q[1] < q[0]\)，\(size = (q[1] - 2) + (N - q[0] - 1) = (q[1] - q[0] - 1) + N - 2\)；

综上：\(size = (q[1] - q[0] - 1 + N - 2) \bmod (N - 2)\)

int size(int q[])
{
    return  (q[1] - q[0] - 1 +  N - 2) % (N - 2);
}

full

实际上，数组能用的空间只有 \(N - 4\)

bool full(int q[])
{
    return size(q) == N - 4;
}

push_left 往左插

void push_left(int q[], int x)
{
    q[q[0]] = x; q[0] = ml(q[0]);
}

push_right 往右插

void push_right(int q[], int x)
{
    q[q[1]] = x; q[1] = mr(q[1]);
}

pop_left 删左边

int top_left(int q[])
{
    return q[mr(q[0])];
}

void pop_left(int q[])
{
    q[0] = mr(q[0]);
}

pop_right 删右边

int top_right(int q[])
{
    return q[ml(q[1])];
}

void pop_right(int q[])
{
    q[1] = ml(q[1]);
}
双端队列-数组版-代码汇总 
const int N = int (1e6 + 10);
int q[N];

void init(int q[])
{
    q[0] = 2, q[1] = 3;
}

int ml(int pos)
{
    return (pos - 5 + N) % (N - 2) + 2;
}

int mr(int pos)
{
    return (pos - 1) % (N - 2) + 2;
}

bool empty(int q[])
{
    return ml(q[1]) == q[0];
}

int size(int q[])
{
    return  (q[1] - q[0] - 1 +  N - 2) % (N - 2);
}

bool full(int q[])
{
    return size(q) == N - 4;
}

void push_left(int q[], int x)
{
    q[q[0]] = x; q[0] = ml(q[0]);
}

void push_right(int q[], int x)
{
    q[q[1]] = x; q[1] = mr(q[1]);
}

int top_left(int q[])
{
    return q[mr(q[0])];
}

void pop_left(int q[])
{
    q[0] = mr(q[0]);
}

int top_right(int q[])
{
    return q[ml(q[1])];
}

void pop_right(int q[])
{
    q[1] = ml(q[1]);
}

结构体版

基于「双链表」实现

结构体定义

struct Node
{
    int v;
    Node* le, * re;
    Node(int val = 0, Node* left = nullptr, Node* right = nullptr)
    {
        v = val; le = left; re = right;
    }
};

init 初始化

Node* head, * tail;

void init()
{
    head = new Node();
    tail = new Node();
    head->re = tail;
    tail->le = head;
}

empty

bool empty()
{
    return head->re == tail;
}

push_left

void push_left(int x)
{
    Node* t = new Node(x, head, head->re);
    head->re->le = t;
    head->re = t;
}

push_right

void push_right(int x)
{
    Node* t = new Node(x, tail->le, tail);
    tail->le->re = t;
    tail->le = t;
}

pop_left

int top_left()
{
    return head->re->v;
}

void pop_left()
{
    Node* p = head->re;
    p->re->le = head;
    head->re = p->re;
    delete p;
}

pop_right

int top_right()
{
    return tail->le->v;
}

void pop_right()
{
    Node* p = tail->le;
    p->le->re = tail;
    tail->le = p->le;
    delete p;
}
结构体版-代码汇总 
 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
struct Node
{
    int v;
    Node* le, * re;
    Node(int val = 0, Node* left = nullptr, Node* right = nullptr)
    {
        v = val; le = left; re = right;
    }
};

Node* head, * tail;

void init()
{
    head = new Node();
    tail = new Node();
    head->re = tail;
    tail->le = head;
}

bool empty()
{
    return head->re == tail;
}

void push_left(int x)
{
    Node* t = new Node(x, head, head->re);
    head->re->le = t;
    head->re = t;
}

void push_right(int x)
{
    Node* t = new Node(x, tail->le, tail);
    tail->le->re = t;
    tail->le = t;
}

int top_left()
{
    return head->re->v;
}

void pop_left()
{
    Node* p = head->re;
    p->re->le = head;
    head->re = p->re;
    delete p;
}

int top_right()
{
    return tail->le->v;
}

void pop_right()
{
    Node* p = tail->le;
    p->le->re = tail;
    tail->le = p->le;
    delete p;
}