如何遍历双端队列并搜索元素？

Question

我有两个这样定义的双端队列

struct elem
{
    int key; elem* next;
}
*left = NULL, *right=NULL, *left2 = NULL, *right2 = NULL;

和推送和弹出功能

void push_front(int n, elem*&l, elem*&r)
{
    elem *p=left;
    left = new elem;
    left -> key=n;
    left -> next=p;
    if(right==NULL)
    {
        right = left;
    }
}

int pop_front(int &n, elem*&l, elem*&r)
{ 
    elem *p; 
if (left)  
{    
    n=left->key; 
    p=left;    
    left=left->next;
    if (left==NULL)
        right=NULL;    
    delete p;     
    return 1;
}   
else
    return 0;
}

我必须输入搜索功能将使用的整数。由于某种原因，他们给了我要求先弹出元素的要求，检查它是否等于输入的数字，然后重复进行直到找到元素或是否已从第一个双端队列中弹出所有元素。在要求之前，我已经这样做了，但是显然这是不正确的：

void search(int x)
{
    elem *y=left;
    while(y->key!=x)
    {
    if(y==right)
    {
        cout<<x<<" wasn't found, adding to front."<<endl;
        push_front(x);
        return;
    }
    y=y->next;
    }
    cout<<x<<" was found"<<endl;
    return;

}

感谢您的帮助。而且也不，我不能使用双端队列库或std :: find或类似的东西。

Answer 1

诸如搜索之类的功能应该只做一件事：报告列表中是否存在该元素。

因此功能应定义为

bool search( const elem * &l, int x )
{
    const elem *current = l;

    while ( current != nullptr && current->key != x ) current = current->next;

    return current != nullptr;
}

基于函数的返回值，您可以将值添加到列表中或执行其他操作。