realalg/linkedlistqueue.cpp at master · jeyong/realalg · GitHub

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

#include <iostream>

using namespace std;

struct Item {
    int val;
    Item* next;
};

struct Queue {
    int size = 0;
    Item* top, *tail = nullptr;
};
void enqueue(unique_ptr<Queue>& q, int val);
void display(unique_ptr<Queue>& q);
void init(unique_ptr<Queue>& q);
int dequeue(unique_ptr<Queue>& q);

int main(int argc, const char * argv[])
{
    auto q = make_unique<Queue>();
    init(q);

    enqueue(q, 1);
    enqueue(q, 2);
    enqueue(q, 3);
    enqueue(q, 4);

    display(q);

    cout<<"dequeue: "<<dequeue(q)<<endl;
    display(q);
    cout<<"dequeue: "<<dequeue(q)<<endl;
    display(q);

}

void init(unique_ptr<Queue>& q) {
    q->size = 0;
    q->top = q->tail = nullptr;
}

void enqueue(unique_ptr<Queue>& q, int val)
{
    auto item = new(Item){.val=val, .next=nullptr};
    q->size++;
    if (q->top==nullptr)
    {
        q->tail = q->top = item;
        return;
    }
    q->tail->next = item;
    q->tail = q->tail->next;
}
int dequeue(unique_ptr<Queue>& q)
{
    if (q->top == nullptr) {
        return INT_MAX;
    }
    q->size--;
    auto item = q->top;
    q->top = q->top->next;
    return item->val;
}
void display(unique_ptr<Queue>& q)
{
    cout<<"Queue Size: "<<q->size<<endl;
    auto cur = q->top;
    while(cur)
    {
        cout<<cur->val<<' ';
        cur = cur->next;
    }
    cout<<endl;
}