Deleting stack element

There's a code:

#include <iostream>
#include <limits>
#include <conio.h>
using namespace std;
struct stack {
    int inf;
    stack *next;
};
int menu();
stack* deleteMaxValue(stack *begin);
int main() {
    stack *begin = NULL;
    while (true) {
        switch (menu())
        {
        case 4:
            begin = deleteMaxValue(begin);
            break;
        case 0:
                return 0;
            break;
        }
    }
}
int menu() {
    cout << "4 - delete max element" << endl;
    cout << "0 - exit" << endl;
    int choise;
    cin >> choise;
    return choise;
}
stack* deleteMaxValue(stack *begin) {
    stack *p = begin;
    stack *t = p->next;
    int max = t->inf;
    while (t != NULL) {
        if (t->inf > max) {
            max = t->inf;
        }
        t = t->next;
    }
    t = begin;
    while (t != NULL) {
        if (t->inf == max) {
            p->next = t->next;
            delete t;
            t = p->next;
        }
        else {
            p = t;
            t = t->next;
        }
    }
    t = begin;
    begin = begin->next;
    delete t;
    return begin;
}

Aim - to delete maximal element of stack. Firstly, I search maximal value, than search the element, which is the same as max and delete it. But in stack, which consists, for example, from

3 2 1

after deleting stays only 1. What's the problem and how can I solve it?

1 answer

  • answered 2018-03-13 21:34 Abhijit Pritam Dutta

    First of all your implementation is not at all a stack. It is simply a link list. A stack is a FILO (first in last out). Just considering it as a normal link list and fixing your issue.

    Your first mistake is:-

    int max = t->inf;// your should take the value of the first node
    

    Correct it to:-

    int max = p->inf;
    

    I have modified your code below check your mistakes:-

    stack* deleteMaxValue(stack *begin) {
        stack *p = begin;
        stack *t = p->next;
        int max = p->inf;//take the value of first element
        while (t != NULL) {
            if (t->inf > max) {
                max = t->inf;
            }
            t = t->next;
        }
    
        t = begin;
        stack *q = t;
        t = t->next;
        p = t->next;
        while (p != NULL) {
            if(q->inf == max){
               begin = t;
               delete q;
            }
            else if (t->inf == max) {
                q->next = p;
                delete t;
               }
            else {
                q = t;
                t = p;
                if(p != NULL)
                    p = p->next;
            }
        }
         /* you don't need this part at all
         t = begin;
         begin = begin->next;
         delete t; */
         return begin;
    }