C++

Forum

 
 
Dynamic Queue - dequeue first element

Mae4ashy (29)
Hello together!

I'm currently writing a code to manipulate linked lists. For that I created the struct Node with a value of type const int and a pointer to the next element and a class Queue, that includes a pointer to the first and a pointer to the last element of the list.

Now I've run into a problem when trying to delete the first element of the queue and return the value of that element. Somehow the function is only deleting the first time i use it correctly and then jumping to either some random other element or directly to the last element.

This is my code so far:
1
2
3
4
5
6
7
8
9
10
11
12
 
  int Queue::dequeue() {

  Node*t = new Node{first->value, first};
 
    if(first == nullptr)
      return 0;
    else{
      t = first;
      first = first -> next;
    }
    return t -> value;
}


Thanks a lot for your help,
Mae
seeplus (6597)
Why is first being passed as a param to Node? Why are you creating a new Node to delete the first element? The memory allocated to t isn't freed so there is a memory leak. When do you free the memory used by the first element? Don't you need something like (not tried):

1
2
3
4
5
6
7
8
9
10
11
 
int Queue::dequeue() {
	if (first == nullptr)
		return 0;

	const auto f{ first };
	const auto v{ f->value };

	first = first->next;
	delete f;
	return v;
}


Mae4ashy (29)
So you're creating a node that is equal to first and a value that is equal to the value of first?
That was what i was trying to do actually. I just didn't know how to initialize Node t. Let me try your suggestion...
Mae4ashy (29)
Okay, so now there is no "Invalid Read" - Error anymore, but given the list with the following values: 23 -1 -4. I want to dequeue the first two, so 23 and -1. But the code deletes 23 and -4. Why?
seeplus (6597)
Post your whole code. There could be other issues.
Mae4ashy (29)
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
 
//Default
Queue::Queue(){
    first = nullptr;
    last = nullptr;
}

//is valid queue?
void Queue::is_valid() const {
    assert(((first==nullptr) && (last == nullptr)) || ((first != nullptr) && (last != nullptr)));
}

//adds element at the end
void Queue::enqueue(int value) {
  
  Node*temp = new Node{value, nullptr};
  
    if(first == nullptr){
      first = temp;
      last = temp;
    }
    else{
      last -> next = temp;
    }
}

//deletes first element & returns its value
int Queue::dequeue() {
  if (first == nullptr)
    return 0;

  const auto f{ first };
  const auto v{ f->value };

  first = first->next;
  delete f;
  return v;
}

//checks if queue is empty
bool Queue::is_empty() const {
    
    if(first == nullptr)
      return true;
    else
      return false;
}

//reverses the node
Node* reverse(Node* n){
  
    if(n == nullptr || n -> next == nullptr)
      return n;
  
    Node*rest = reverse(n->next);
    n->next->next = n;
    
    n->next = nullptr;
    return rest;
}

//prints reversed queue
void print_nodereverse(std::ostream& os, Node* n) {
    if (n != nullptr) {
        os << " " << n->value;
        print_nodereverse(os, n->next);
    }
}
*/
void Queue::print_reverse(std::ostream& os) const {
  
    Node*n = reverse(first);
    
    os << "[";
    if (n != nullptr) {
        os << n->value;
        print_nodereverse(os, n->next);
    }
    os << "]";
    
}


seeplus (6597)
The whole, compilable program - including Queue class definition, Node, main() etc etc!

Mae4ashy (29)
Ah sorry, here it is. Thanks a lot for helping :)

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
 
struct Node {
    Node(const int _value, Node* _next) : value(_value), next(_next) { }
    const int value;
    Node* next;
};

class Queue {
public:
    // PRE:  -
    // POST: Valid and empty queue.
    Queue();

    // PRE:  Valid queue.
    // POST: Valid queue with new node having value i added at end of queue.
    void enqueue(int value);

    // PRE:  Valid and non-empty queue.
    // POST: Removes first node from queue.
    //       Returns content of first node.
    int dequeue();

    // PRE:  Valid queue.
    // POST: Returns true if queue is empty, false otherwise.
    bool is_empty() const;

    // PRE:  Valid queue.
    // POST: Outputs queue content to os in sequence from first to last.
    void print(std::ostream& os) const;
    
    // PRE: Valid queue
    // POST: Outputs queue content to os in reverse order, from last to first.
    void print_reverse(std::ostream& os) const;

private:

    // Class invariant: first == nullptr iff last == nullptr
    Node* first; // pointer to first element of queue or nullptr is queue is empty.
    Node* last;  // pointer to last element of queue or nullptr if queue is empty.

    // PRE: -
    // POST: Ensures class invariant.
    void is_valid() const;
};


#endif

int main() {
    Queue q;

    // parse and process the test data until the end marker occurs.
    // The format of the test data is:
    // <function> <parameter>
    // where <parameter> is optional and specific to the function.
    while (std::cin.good()) {

        // get <function>, exit if end marker occurs
        std::string function;
        std::cin >> function;
        if (function == "end") {
            break;
        }

        if (function == "dequeue") {
            std::cout << q.dequeue() << "\n";

        } else if (function == "enqueue") {
            int value; // parameter "value"
            std::cin >> value;
            q.enqueue(value);

        } else if (function == "is_empty") {
            std::cout << q.is_empty() << "\n";

        } else if (function == "print_reverse") {
            q.print_reverse(std::cout);
            std::cout << "\n";

        } else {
            std::cout << "unknown function: " << function << "\n";
            break;
        }
        
    }
    return 0;
}
seeplus (6597)
There is a problem in enqueue. Have a look at this (reverse/print-reverse not tried):

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
 
#include <iostream>

struct Node {
	//Node(const int _value, Node* _next) : value(_value), next(_next) { }
	Node(int _value) : value(_value) {}

	const int value{};
	Node* next{};
};

class Queue {
public:
	Queue();
	void enqueue(int value);
	int dequeue();
	bool is_empty() const;
	void print(std::ostream& os) const;
	void print_reverse(std::ostream& os) const;

private:
	Node* first; // pointer to first element of queue or nullptr is queue is empty.
	Node* last;  // pointer to last element of queue or nullptr if queue is empty.

	void is_valid() const;
};

//Default
Queue::Queue() {}

//is valid queue?
void Queue::is_valid() const {
	//assert(((first == nullptr) && (last == nullptr)) || ((first != nullptr) && (last != nullptr)));
}

//adds element at the end
void Queue::enqueue(int value) {
	const auto temp{ new Node{ value} };

	if (first == nullptr) {
		first = temp;
		last = temp;
	} else {
		last->next = temp;
		last = temp;
	}
}

//deletes first element & returns its value
int Queue::dequeue() {
	if (first == nullptr)
		return 0;

	const auto f{ first };
	const auto v{ f->value };

	first = first->next;
	delete f;
	return v;
}

//checks if queue is empty
bool Queue::is_empty() const {
	return first == nullptr;
}

void Queue::print(std::ostream& os) const {
	for (auto n = first; n != nullptr; n = n->next)
		os << n->value << ' ';
}


//reverses the node
Node* reverse(Node* n) {
	if (n == nullptr || n->next == nullptr)
		return n;

	Node* rest = reverse(n->next);
	n->next->next = n;
	n->next = nullptr;
	return rest;
}

//prints reversed queue
void print_nodereverse(std::ostream& os, Node* n) {
	if (n != nullptr) {
		os << " " << n->value;
		print_nodereverse(os, n->next);
	}
}

void Queue::print_reverse(std::ostream & os) const {

	Node* n = reverse(first);

	os << "[";
	if (n != nullptr) {
		os << n->value;
		print_nodereverse(os, n->next);
	}
	os << "]";
}


int main() {
	Queue q;

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

	q.print(std::cout);
	auto e{ q.dequeue() };

	std::cout << '\n' << e << '\n';
	q.print(std::cout);

	return 0;

	// parse and process the test data until the end marker occurs.
	// The format of the test data is:
	// <function> <parameter>
	// where <parameter> is optional and specific to the function.
	for (std::string function; std::cin >> function; ) {
		if (function == "end")
			break;

		if (function == "dequeue") {
			std::cout << q.dequeue() << "\n";
			continue;
		}

		if (function == "enqueue") {
			int value{};
			std::cin >> value;
			q.enqueue(value);
			continue;
		}

		if (function == "is_empty") {
			std::cout << q.is_empty() << "\n";
			continue;
		}

		if (function == "print_reverse") {
			q.print_reverse(std::cout);
			std::cout << "\n";
			continue;
		}

		std::cout << "unknown function: " << function << "\n";
		break;

	}
}



1 2 3 4
1
2 3 4

Mae4ashy (29)
Ahhh i see, i forgot to reassign 'last'. Oh wow thanks a lot, now it is working very well!
Topic archived. No new replies allowed.