I implemented a queue with linked list, and I want multiple threads to push elements in the correct order. I used mutex to lock my member functions, but the numbers printed to terminal is still not in correct order, which should be 1,2,3,4,5,6. Insteads it prints a wrong order, such as 3,1,4,2,5,6. This means the mutex lock DIDNT work. Can someone please tell me why? And how to fix this?
// Implement a queue<int>，need functions: push_front, back, pop_back, and print
#include <iostream>
#include <thread>
#include <mutex>
using namespace std;
struct ListNode {
ListNode* next;
int val;
ListNode(int x) {
val = x;
this->next = nullptr;
}
};
class Queue {
public:
Queue() {
head = new ListNode(0); // dummy head
tail = head;
}
void push_front(int x) { // add node at then end of linked list
lock_guard<mutex> lock(m);
tail->next = new ListNode(x);
tail = tail->next;
}
int pop_back() { // remove the first node of the linked list
lock_guard<mutex> lock(m);
ListNode* back = head->next;
if (back == nullptr) {
throw invalid_argument("empty queue");
}
head->next = back->next;
back->next = nullptr;
return back->val;
}
void print() {
lock_guard<mutex> lock(m);
ListNode* p = head->next;
while (p != nullptr) {
cout << p->val << endl;
p = p->next;
}
}
private:
mutable mutex m;
// Implement with linked list
ListNode* head;
ListNode* tail;
};
int main() {
Queue* queue = new Queue();
// Multiple threads push at the same time --> order is wrong
thread t1 = thread(&Queue::push_front, queue, 1);
thread t2 = thread(&Queue::push_front, queue, 2);
thread t3 = thread(&Queue::push_front, queue, 3);
thread t4 = thread(&Queue::push_front, queue, 4);
thread t5 = thread(&Queue::push_front, queue, 5);
thread t6 = thread(&Queue::push_front, queue, 6);
t1.join();
t2.join();
t3.join();
t4.join();
t5.join();
t6.join();
queue->print();
}
