Решение задачи со стеками о очередью с помощью динамических списков

Question

Изучаю C++ и мне нужно решить задачу, представляя очередь и стек как динамические списки. Задача: Даны два стека целых чисел от 0 до 1000. Из элементов пеpвого стека, котоpых нет во втоpом сфоpмиpовать очеpедь.

Я понимаю как инициализировать стек и очередь и необходимую функции для работы, но как реализовать функцию, которая сравнивает стеки и кладёт их элементы в очередь я понятия не имею. Не знаю есть ли смысл в написании кода в вопросе, потому что он просто не готов но всё равно его здесь. Вдруг поможет.

#include <iostream>
#include <ctime>

using namespace std;

struct Stack {
    int data;
    Stack* next;
};

void InitStack(Stack*& top) {
    top = NULL;
}

void push(Stack*& top, int value) {
    Stack* tmp = new Stack;
    tmp->next = top;
    top = tmp;
    top->data = value;
}

int pop(Stack*& top) {
    Stack* tmp = top;
    int d = top->data;
    top = top->next;
    delete(tmp);
    return d;
}

bool Empty(Stack*& top) {
    return (top == NULL);
}

void  nullStack(Stack*& top) {
    Stack* tmp;
    while (!Empty(top)) {
        tmp = top;
        top = top->next;
        delete(tmp);
    }
}
void print(Stack*& top) {
    if (!Empty(top)) {
        Stack* tmp = top;
        while (!Empty(tmp)) {
            cout << tmp->data << " ";
            tmp = tmp->next;
        }
        cout << endl;
        delete(tmp);
    }
    else {
        cout << "Стек пуст!\n";
    }
}
class Queue {
private:
    struct Node
    {
        int data;
        Node* next;
    };
    Node* head, * tail;

public:
    Queue() {
        head = NULL;
        tail = NULL;
    }

    bool empty() {
        return head == NULL;
    }

    void add(int value) {
        if (empty()) {
            head = new Node;
            head->data = value;
            head->next = NULL;
            tail = head;
        }
        else {
            tail->next = new Node;
            tail = tail->next;
            tail->data = value;
            tail->next = NULL;
        }
    }

    int del() {
        if (empty()) {
            cout << "Очередь пуста!\n";
            return 0;
        }
        else {
            int d = head->data;
            Node* tmp = head;
            head = head->next;
            delete tmp;
            return d;
        }
    }

    void nullQueue() {
        Node* tmp;
        while (!empty()) {
            tmp = head;
            head = head->next;
            delete tmp;
        }
    }

    void print() {
        Node* temp = head;     
        while (temp != NULL)
        {
            cout << temp->data << " "; 
            temp = temp->next;
        }
        cout << endl;
    }
    
};
int main() {
    return 0;
}

Answer 1

Пусть у вас есть стеки А и В. Создайте дополнительный стек С.

Теперь извлекаете по одному элементу из А, потом сравниваете с ним все элементы B, перекидывая их в стек С. Если не нашли аналога =- кладёте элемент из A в очередь.

На следующем шаге берёте новый элемент из А, а сравниваете с элементами из C, перекладывая их в В.

И т.д., пока A не кончится.

Answer 2

Явно тут многое неправильно, но оно выполняет примерно то, что нужно в задании. Правда тут не выполнена инициализация 1000 элементов, а просто вводится по 10 элементов для каждого стека.

#include <list>
#include <iostream>
#include <algorithm>
#include <iterator>

using namespace std;

struct Stack
{
    list <int> data;

    int push(int num)
    {
        data.push_back(num);
        return 0;
    }
    int pop()
    {
        int i = data.back();
        data.pop_back();
        return i;
    }
};

struct Queue
{
    list <int> data;

    int enqueue(int num)
    {
        data.push_back(num);
        return 0;
    }
    int dequeue()
    {
        int i = data.front();
        data.pop_front();
        return i;
    }
};


int main()
{
    Stack A, B;
    Queue result;
    
    string input;
    int num;

    list <int> :: iterator itA;
    list <int> :: iterator itB;
    bool found = false;

    for(int i=0;i<10;i++)
    {
        cin>>num;
        cout<<i<<endl; 
        A.push(num);
    }
    cout << "Введите второй стек"<<endl;
    
    for(int i=0;i<10;i++)
    {
         cin>>num;
         cout<<i<<endl;
         B.push(num);
    }

    for(itA=A.data.begin();itA!=A.data.end();itA++)
    {
        found = false;
        for(itB=B.data.begin();itB!=B.data.end();itB++)
            if((*itA) == (*itB)){found=true;break;}
        if(!found)
            result.enqueue(*itA);
    }

    cout << "Результат работы: "<<endl;
    for(int i: result.data)
        cout << i << endl;
}

БЛОГ НА HUSL

Решение задачи со стеками о очередью с помощью динамических списков

Ответы (2 шт):