CODEWITHSUNDEEP
c++
B-Mac
B-Mac

Reputation: 567

Something looks wrong in this implementation of stack but it works fine

I have this assignment where I need to implement a stack using arrays (easy as you like) but three of the methods have already been provided and I just need to implement the remaining two functions: peek() and flush().

However, I don't quite seem to agree with the implementation of pop provided. I mean, when you pop without any elements inside (N == 0), then it would mean something like Array[-1] and the program should crash but it doesn't. Please explain how this (not crashing) happens.

class STACK {
    private:
        int* s;
        int N;
    public:
        STACK(int maxN) {
            s = new int[maxN]; 
            N = 0;
        }
        int empty() const {
            return N == 0;
        }
        void push(int item) {
            s[N++] = item;
        }
        int peek() {
            /* implement this part */
        }
        int pop() {
            return s[--N];
        }
        void flush() {
            /* also implement this part */

        }
};

Upvotes: 0

Views: 38

Answers (2)

Mark B
Mark B

Reputation: 96311

You're right. The pop function as written will fail when the stack is empty.

Accessing data prior to the start of an array is undefined behavior, which does mean exactly that. It can do anything including not crashing.

Upvotes: 1

Mike Seymour
Mike Seymour

Reputation: 254751

I don't quite seem to agree with the implementation of pop provided.

It has a pre-condition: it must not be called if the stack is empty. Whether to enforce that precondition (with a runtime cost to check it) or just document it (with a risk of invalid behaviour) is a design decision for you to make.

Please explain how this (not crashing) happens.

Undefined behaviour doesn't necessarily cause the program to crash. If there's addressable memory before the array, then s[--N] will (almost certainly) just read what's there. If there isn't, then it might crash.

Upvotes: 1

Related Questions