Почему не решается задача.Стек,С++

207

06 апреля 2018, 18:44

Всем привет. Есть задача , если запустить через консоль , то всё выдает как нужно. Но на системе проверки задач, пишет что мол Time Limit , мол много времени занимается. Может как-то можно оптимизировать код ? P.S try;catch нельзя применять. Условие задачи :https://ibb.co/h6EUnH

 #include <iostream>
 #include <string>
using namespace std;
struct Node
{
int data;
Node *next;
};
struct Queue
{
int size;
Node* first;
Node* last;
};
void Creation(Queue*Q)
{
Q->first = new Node;
Q->first->next = NULL;
Q->last = Q->first;
Q->size = 0;
}
int Size(Queue *Q)
{
return Q->size;
}
 void Clear(Queue* Q)
 {
Q->first->next = NULL;
Q->last = Q->first;
Q->size = 0;
}
void exit(Queue* Q)
{
cout << "bye";
}
void Add(Queue*Q)
{
int value;
cin >> value;
Q->last->next = new Node;
Q->last = Q->last->next;
Q->last->data = value;
Q->last->next = NULL;
Q->size++;
}
void delete_first(Queue*Q)
{
if (Q->first->next == NULL) cout << "error";
else cout << Q->first->next->data;
Q->first = Q->first->next;
Q->size--;
}
void front(Queue*Q)
{
if (Q->size == 0) cout << "error";
else cout << Q->first->next->data;
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
Queue Q;
Creation(&Q);
string valuable;
while (valuable != "exit")
{
    cin >> valuable;
    if (valuable == "push")
    {
        Add(&Q);
        cout << "ok\n";
    }
    else if (valuable == "pop")
    {
        delete_first(&Q);
        cout << endl;
    }
    else if (valuable == "front")
    {
        front(&Q);
        cout << endl;
    }
    else if (valuable == "size")
    {
        cout << Size(&Q);
        cout << endl;
    }
    else if (valuable == "clear")
    {
        Clear(&Q);
        cout << "ok\n";
    }
    else if (valuable == "exit")
    {
        exit(&Q);
        break;
    }
}
return 0;

Answer 1

Чтобы программа работала быстрее, нужно функции сделать встраиваемым, избавиться от лишных переменных, а также лишных вызовов всяческих функций. Для того, чтоб добиться лучших результатов, лучше все функции сделать членами класса и не забывать о корректности. Конструктор классов вызывает конструкторы содержащихся обьектов с дефолтными значениями, и потом не приходится их инициализировать:

struct Node
{
    int data;
    Node *next;
    Node() : data(0), next(0) {}
};
// пусть конструктор создаст уже инициализированные обьекты,
// чтоб потом не присваивать им ноль
class Queue
{
    int size;
    Node* first;
    Node* last;
public:
    Queue()  : size(0), first(0), last(0) {}
    ~Queue() {
        while (size) {
            Node* t = first;
            first = first->next;
            delete t;
            --size;
        }
        std::cout << "ok\n";
    }
void Add(int value)
{
    if (!first) {
        first = new Node;
        first->data = value;
        last = first;
    }
    else {
        last->next = new Node;
        last = last->next;
        last->data = value;
    }
    ++size;
}
void delete_first()
{
    if(!first) {
        std::cout << "error\n";
        return;
    }
    Node* t = first;
    first = first->next;
    delete t;
    --size;
}
// в конце определяем селекторы, (не меняют состояние обьекта)
const Node& front() const
{
    if (!size) std::cout << "error";
    return *first;
}
int  Size() const   { return  size;  }
void exit() const   { std::cout << "bye"; }
};

Как вы заметили, очень много лишнего тут уже нет. Также в программе:

using namespace std;
int main()
{   
    Queue Q;
    string valuable;
    // цикл должен завершиться, если даже мы забудем вводить "exit"
    // уже все функции вызываем для одного обьекта очереди, 
     // а не создаем много  таких
    while (cin >> valuable && valuable != "exit")
    {
        if (valuable == "push")
        {
            cout << "enter value ";
            int val = 0;
            cin >> val;
            // вводим узел с полем val
            Q.Add(val);
            cout << "ok\n";
        }
        else if (valuable == "pop")
        {
            Q.delete_first();
            cout << endl;
        }
        else if (valuable == "front")
            cout <<  Q.front().data << endl;
        else if (valuable == "size")
            cout << Q.Size() << endl;
        else if (valuable == "clear")
            Q.~Queue();
        else if (valuable == "exit")
            Q.exit();
    }
    return 0;
}

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