1

Получилось только просто сделать классический стек.

#include <iostream> 
using namespace std;

struct Node
{
 int d;
 Node *p;
};

Node * first(int d);
void push(Node **top, int d);
int pop(Node **top);

void main()
{
 Node* top = first(1);
 for (int i = 2; i<6; i++) push(&top, i);
 while (top) 
   cout << pop(&top) << " ";
}


Node * first(int d)
{
 Node *pv = new Node;
 pv->d = d;
 pv->p = 0;
 return pv;
}


void push(Node **top, int d)
{
 Node *pv = new Node;
 pv->d = d;
 pv->p = *top;
 *top = pv;
}

int pop (Node **top)
{
 int temp = (*top)->d;
 Node *pv = *top;
 *top = (*top)->p;
 delete pv; 
 return temp;
}
5
  • можно сказать, что и это не удалось. Commented 11 мая 2018 в 17:06
  • @ARHovsepyan Жаль
    – Elrion
    Commented 11 мая 2018 в 17:18
  • расшифруйте понятие вывести, элемент должен удаляться из стека как в вашем примере, или просто вывести? Если последовательно читать и удалять, то у вас уже все реализовано, достаточно проверить возвращаемое значение функции на pop на %3 == 0. Если же нужно читать и только удалять элементы, кратные 3, то тогда нужен дополнительный кеш. Commented 11 мая 2018 в 17:34
  • @Alexcei Shmakov Читать и только удалять элементы, кратные 3. Пытался в другой стек перенести, но не получается.
    – Elrion
    Commented 11 мая 2018 в 18:00
  • Итератором наверное
    – user245150
    Commented 11 мая 2018 в 18:57

1 ответ 1

1
  1. Используя дополнительный стек, это можно сделать следующим образом.

    void main()
    {
       Node* top = first(1);
       for (int i = 2; i<20; i++) 
          push(&top, i);
       Node * top2 = nullptr;
       while (top)
       {
           int d = pop(&top);
           if (d % 3)
              push(&top2, d);
       }
    
       while (top2)
       {
           push(&top, pop(&top2));
       }
       // вывод результирующего массива(он не содержит элементов, кратных 3)
       while (top)
           cout << pop(&top) << " ";
    }
    

Суть работы: читаем из первого стека, и добавляем в другой стек только те элементы, которые не кратны 3. В результате во вспомогательном стеке останутся только элементы, не кратные 3.
Все что остается сделать, это перенести из вспомогательного стека обратно в основной.

Этот вариант решения является неоптимальный(но рабочий), так как приходится использовать вспомогательный стек. Можно обойтись без вспомогательного стека.

  1. Без использование дополнительного стека

    void main()
    {
        Node* top = first(1);
        for (int i = 2; i<20; i++) 
            push(&top, i);
        while (top && top->d % 3 == 0)
           pop(&top);
        Node *els = top;
        while (els)
        {
           if (els->p && els->p->d % 3 == 0)
           {
               Node* remove = els->p;
               els->p = els->p->p;
               delete remove;
           }
           els = els->p;
        }
        while (top)
            cout << pop(&top) << " ";
      }
    

Суть работы:
а)сначала удаляем верхний элемент стека, если он кратен 3. Это нужно для того, чтобы получить актуальную голову после возможного удаления.
б) имея актуальную голову после удаления, далее бежим по стеку вниз и смотрим, если для родителя текущего элемента элемент кратен 3 - значит родителя удаляем.У текущего элемента изменяем родителя на следующий элемент после удаляемого.

1
  • Спасибо. Буду разбираться в этом.
    – Elrion
    Commented 11 мая 2018 в 19:35

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.