Shury Shury - 19 days ago 6
C++ Question

Pop front and back in deque

I'm trying to implement a deque with some functions: front(),
back(), push_front(), push_back(), pop_front(), pop_back(). If I have one element in the queue and I try to pop it I get an "read access violation" in print function, however I check if a first element exists in deque.

#include<iostream>
#include<cstdlib>
using namespace std;

struct Nod {
int info;
Nod* next, *back;
};

void create_queue(Nod*& p, Nod*& u)
{
Nod *c = new Nod;
cout << "c->info: "; cin >> c->info;
if (!p)
{
p = c;
p->back = NULL;
p->next = NULL;
u = p;
}
else
{
u->next = c;
c->back = u;
u = c;
u->next = NULL;
}
}

void print_queue(Nod* p, Nod* u)
{
if (p) {
Nod *c = p;
while (c) {
cout << c->info << " ";
c = c->next;
}
}
else
cout << "Deque is empty";
}

int front(Nod *p) {
return p->info;
}

int back(Nod *u) {
return u->info;
}

void push_front(Nod*& p, Nod*& u) {
Nod *c = new Nod;
cout << "Push front c->info "; cin >> c->info;
c->next = p;
p->back = c;
c->back = NULL;
p = c;
}

void push_back(Nod*& p, Nod*& u) {
Nod *c = new Nod;
cout << "Push back c->info "; cin >> c->info;
c->back = u;
u->next = c;
u = c;
u->next = NULL;
}

void pop_front(Nod*& p, Nod*& u) {
if (p) {
Nod *c = p;
if (p->next != NULL) {
p->next->back = NULL;
p = p->next;
}
delete c;
}
else
{
cout << "Can't pop, deque is empty";
}
}

void pop_back(Nod*& p, Nod*& u) {
if (u){
Nod *c = u;
if (u->back != NULL) {
u->back->next = NULL;
u = u->back;
}
delete c;
}
else
{
cout << "Can't pop, deque is empty";
}
}

int main()
{
int n, i = 1;
Nod *p, *u = new Nod;
p = NULL;
u = NULL;
cout << "Nr nod: "; cin >> n;
while (i <= n){
create_queue(p, u);
i++;
}
pop_front(p, u); //problems if there is only one element in deque
print_queue(p, u);
system("Pause");
}

Answer

When there's only one node, you delete it but it's never set to nullptr, thus you still access the memory there causing a runtime error. Here I've written a modified pop_front and pop_back. In particular pop_back now sets the next pointer of the tail's previous element to nullptr. If there is only one element in the deque (head == tail) we do a pop_front, which will set head to nullptr by assigning it to its next element.

void pop_front(Nod*& head, Nod* tail) {
    if (head) {
        Nod* nodePtr = head;
        head = head->next;
        delete nodePtr;
    }
}

void pop_back(Nod*& head, Nod* tail) {
    if (head == tail) {
        return pop_front(head, tail);
    }
    tail->back->next = NULL;
    delete tail;
}