为什么这个双端队列数据结构会引发读取访问冲突

Question

我有大学作业，其中我必须使用不是来自 std/stl 库的双端队列。我从他们卖给我的大学指南中复制了代码，但是当我测试它时，我收到读取访问冲突错误。这是代码：

#include <iostream>
using namespace std;

struct deque
{
    int key;
    deque *next_element;

} *LEFT = NULL, *RIGHT = NULL;

void push_LEFT(int x);
void push_RIGHT(int x);
int pop_LEFT(int &x);
int pop_RIGHT(int &x);

int main()
{
    int temp;
    push_LEFT(1);
    push_LEFT(2);
    push_LEFT(3);
    push_LEFT(4);

    pop_LEFT(temp);
    cout << temp << endl;
    pop_LEFT(temp);
    cout << temp << endl;
    pop_LEFT(temp);
    cout << temp << endl;
    pop_LEFT(temp);
    cout << temp << endl;
    system("pause");
}

void push_LEFT(int x)
{
    deque *ex;
    ex = LEFT;
    LEFT = new deque;
    LEFT->key = x;
    if (RIGHT == NULL)
    {
        RIGHT = LEFT; 
    }

}

void push_RIGHT(int x)
{
    deque *ex;
    ex = RIGHT;
    RIGHT = new deque;
    RIGHT->key = x;

    if (LEFT == NULL)
    {
        LEFT = RIGHT;
    }

    else
    {
        ex->next_element = RIGHT;
    }

}

int pop_LEFT(int &x)
{
    deque *ex;
    if (LEFT)
    {
        x = LEFT->key;
        ex = LEFT;
        LEFT = LEFT->next_element;
        if (LEFT == NULL)
        {
            RIGHT = NULL;
        }
        delete ex;
        return 1;
    }
    else
    {
        return 0;
    }
}

int pop_RIGHT(int &x)
{
    deque *ex;
    if (RIGHT)
    {
        x = RIGHT->key;
        if (LEFT == RIGHT)
        {
            delete RIGHT;
            LEFT = RIGHT = NULL;
        }
        else
        {
            ex = LEFT;
            while (ex->next_element != RIGHT)
            {
                ex = ex->next_element;
            }
            x = RIGHT->key;
            ex->next_element = NULL;
            delete RIGHT;
            RIGHT = ex;
        }
        return 1;
    }
    else
    {
        return 0;
    }
}

我认为 push 函数可以工作，问题出在 pop 函数中，因为那里抛出了异常。提前致谢！

Answer 1

我认为你书中的例子是完全错误的，稍加修正就不能正确，因此我为你写了一个新代码。我认为您正在寻找一个带有 push 和 pop 方法的简单队列。我只在你的代码中写了一个方向队列或左一个，你可以根据需要扩展右一个。

#include <iostream>
using namespace std;

struct deque
{
    int key;
    deque *next_element=NULL;

} *LEFT = NULL;

void push_LEFT(int x);
void pop_LEFT(int &x);


int main()
{
    int temp;
    push_LEFT(1);
    push_LEFT(2);
    push_LEFT(3);
    push_LEFT(4);

    pop_LEFT(temp);
    cout << temp << endl;
    pop_LEFT(temp);
    cout << temp << endl;
    pop_LEFT(temp);
    cout << temp << endl;
    pop_LEFT(temp);
    cout << temp << endl;
    system("pause");
}

void push_LEFT(int x)
{

    if (LEFT== NULL)
    {
        LEFT = new deque;
        LEFT->key = x;
        LEFT->next_element = NULL;
    }
    else
    {
        deque* ext=LEFT;
        while (ext->next_element!=NULL)
        {
            ext = ext->next_element;
        }
        ext->next_element = new deque;
        ext->next_element->key = x;
    }
}

void pop_LEFT(int &x)
{
    if (LEFT)
    {
        x = LEFT->key;
        delete Left; 
        LEFT = LEFT->next_element;
    }
}

为什么这个双端队列数据结构会引发读取访问冲突

Why this deque data structure thows read access violation

c++

access-violation

deque