在双端队列中弹出前后

Question

我正在尝试使用一些函数实现双端队列：front()，返回（），push_front（），push_back（），pop_front（），pop_back（）。如果我在队列中有一个元素并尝试弹出它，我会在打印函数中得到一个 "read access violation"，但是我会检查双端队列中是否存在第一个元素。

#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 1

当只有一个节点时，你delete它但它永远不会设置为nullptr，因此你仍然访问那里的内存导致运行时错误。这里我写了修改后的pop_front和pop_back。特别是 pop_back 现在将尾部前一个元素的 next 指针设置为 nullptr。如果双端队列 (head == tail) 中只有一个元素，我们会执行 pop_front，这会将 head 分配给下一个元素，从而将 nullptr 设置为 nullptr。

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);
    }
    Nod* prev = tail->back;
    prev->next = NULL;
    delete tail;
    tail = prev;
}

在双端队列中弹出前后

Pop front and back in deque

c++

deque