Стек на 100 элементов

Question

при написании стека на 100 элементов столкнулся с проблемой.

Если добавляю 100 элементов и вызываю метод POP мне почему то возвещает 2 индекса 100 и 99 (как и должно).

Если дальше вызвать метод PUSH с любым числом то это число станет индексом, а не запишется в стек.

Сам код:

#include <iostream>
#include <string>
#include <cstdlib>

#define MAX 100

struct stack {
    int elemnt[MAX];
    int top;
};


class STACK {
public:static void INIT(struct stack *stk) {
        stk->top = 0;
    }

public:static int PUSH(struct stack *stk, int x) {
        if (stk->top > MAX) {
            return 1;
        } else {
            stk->top++;
            stk->elemnt[stk->top] = x;
        }
        return 1;
    }

public:static int POP(struct stack *stk) {
        if(STACK_EMPTY(stk))
            return 1;
        else {
            stk->top--;
            return stk->elemnt[stk->top + 1];
        }
}

public:static int TOP(struct stack *stk) {
        if(stk->top > 0) {
            return stk->elemnt[stk->top-1];
        } else {
            return 0;
        }
}

public:static int SIZE(struct stack *stk) {
        return stk->top;
    }

public:static bool STACK_EMPTY (struct stack *stk) {
        if(stk->top == 0)
            return true;
        else
            return false;
    }

public:static void CLEAR (struct stack *stk) {
        while (!STACK_EMPTY(stk)) {
            POP(stk);
        }
    }

public:static void PRINT(struct stack *stk) {
    int i = stk -> top;
        while (!STACK_EMPTY(stk)) {
            std::cout << stk->elemnt[i] << "\n";
            i--;
            stk->top--;
        }
    }
};


int main() {
    std::string push = "PUSH";
    std::string pop = "POP";
    std::string end = "END";

    int number;
    struct stack *stk;
    stk = (struct stack*)malloc(sizeof(struct stack));
    STACK::INIT(stk);
    int exception = 0;

    while (true) {
        std::string inp;
        std::cin >> inp;

        if(inp == push) { //PUSH
            std::cin >> number;
            if(STACK::SIZE(stk) >= 0 && STACK::SIZE(stk) < MAX) {
                STACK::PUSH(stk, number);
            } else {
               exception++;
            }
        }

        else if(inp == pop) { //POP
            if(!STACK::STACK_EMPTY(stk)) {
                STACK::POP(stk);
            } else {
               exception++;
            }
        }

        else if(inp == end) {
            if(exception <= 0) {
                STACK::PRINT(stk);
            } else {
                std::cout << "error";
            }
            break;
        }
    }
}

Answer 1

По сути:

if (stk->top > MAX) {
    return 1;
} else {
    stk->top++;
    stk->elemnt[stk->top] = x;
}

Тут у вас получается, что вы вносите в массив элемент за пределы массива. Выделено MAX элементов. Пусть top - вообще MAX, даже не MAX-1 - итог: вы входите во вторую ветку, теперь top становится MAX+1 и вы пишете в elemnt[MAX+1] - в то время как последний элемент - elemnt[MAX-1].

Все. Запись за пределами массива - UB.

P.S. А вот как мог бы выглядеть ваш стек с максимальным приближением к вашему проекту и функциональности.

#include <iostream>
#include <string>

using namespace std;

#define MAX 100

class stack
{
public:
    stack():top_(0){}
    void push(int x)
    {
        if (top_ == MAX) throw range_error("push");
        elemnt[top_++] = x;
    }
    int pop()
    {
        if (top_ == 0) throw range_error("pop");
        return elemnt[--top_];
    }
    int top() const
    {
        if (top_ == 0) throw range_error("top");
        return elemnt[top_-1];
    }
    int size() const { return top_; }
    bool empty() const { return size()==0; }
    void clear() { top_ = 0; }

    void print() const
    {
        for(int i = top_-1; i >=0 ; --i)
            cout << elemnt[i] << "\n";
    }

private:
    int elemnt[MAX];
    int top_;
};

int main() {
    std::string push = "PUSH";
    std::string pop = "POP";
    std::string end = "END";

    int number, excpt = 0;
    stack stk;

    while (true) {

        std::string inp;
        std::cin >> inp;

        if(inp == push) { //PUSH
            std::cin >> number;
            try {
                stk.push(number);
            } catch(exception&) {
               excpt++;
            }
        }
        else if (inp == pop) { //POP
            try {
                stk.pop();
            } catch(exception&) {
               excpt++;
            }
        }
        else if(inp == end) {
            if( excpt <= 0) {
                stk.print();
            } else {
                std::cout << "error";
            }
            break;
        }
    }
}

БЛОГ НА HUSL

Стек на 100 элементов

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