Starry Wintersky

小星星starry的个人网站

0%

C/C++ STL stack/queue

发表于 分类于 热度： 讨论区：
C/C++版本的stack/queue/priority_queue用法。

stack和queue大概由deque实现。priority_queue由堆实现。

初始化

1
2
3
4
5
6
stack<int>stk;
while(!stk.empty())stk.pop();
queue<int>que;
while(!que.empty())que.pop();
priority_queue<int>tq;
while(!tq.empty())tq.pop();

插入

1
2
3
stk.push(x);
que.push(x);
tq.push(x);

删除

1
2
3
stk.pop(x);
que.pop(x);
tq.pop(x);

取顶部元素

1
2
3
int x = stk.top();
int y = que.front();
int z = tq.front();

取底部元素

1
int y2=que.back(); // 大惊喜，糟糕的是priority_queue没有实现这个操作。

优先队列的细节

1
2
3
priority_queue<int, vector<int>, greater<int> >pq;
// 类型，容器，运算符
// 默认是*降序*，greater为升序，less为降序。

小根堆初步代码实现

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
# include <queue>
# include <cstdio>
#  include <cstring>
using namespace std;
class NodeTree
{
public:
    int var;
};
class Heap
{
public:
    NodeTree treenode[1005];
    int length;
    Heap()
    {
        length = 0;
        memset(treenode, 0, sizeof(treenode));
    }
    void insert_heap(int number)
    {
        length++;
        treenode[length].var = number;
    }
    int modify_heap(int i)
    {
        int now=i;
        int left = 2*i, right=2*i+1;
        if(right > length){
            if(left <= length && treenode[left].var < treenode[now].var){swap(treenode[left].var, treenode[now].var);return 1;}
            else return 0;
        }
        else{
            if(treenode[left].var > treenode[right].var && treenode[right].var < treenode[now].var){swap(treenode[right].var, treenode[now].var);return 2;}
            else if(treenode[left].var <= treenode[right].var && treenode[left].var < treenode[now].var){swap(treenode[left].var, treenode[now].var);return 1;}

        }
        return 0;
    }
    void build_heap(vector<int> number)
    {
        for(int i = 0; i < number.size(); i++){
            insert_heap(number[i]);
            for(int i = length; i > 0; i--)
                modify_heap(i);
        }
//        printf("build complete\n");
//        for(int i = 1; i <= length; i++){
//            printf("%d-", treenode[i]);
//        }
//        printf("\n");
    }
    void push(int i){
        insert_heap(i);
        for(int i = length; i > 0; i>>=1)
            modify_heap(i);
    }
    int top()
    {
        return treenode[1].var;
    }
    void pop()
    {
        treenode[1].var = treenode[length].var;
        length--;
        for(int i = 1; i <= length; ){
            int p = modify_heap(i);
            if(p == 0)break;
            if(p == 1)i *= 2;
            if(p == 2)i = 2*i+1;
        }
        return;
    }
    bool empty()
    {
        return length==0;
    }
};
int main()
{
    vector<int>number={39,24,12,64,2,67,34,77,25,23, 29, 66};
    Heap heap;
    heap.build_heap(number);

    while(!heap.empty())
    {
        printf("=%d=", heap.top());
        heap.pop();
    }
    return 0;
}

-------------这么快就看完啦^ω^谢谢阅读哟-------------