Pop Array-based Stack

[codeyy]

I am trying to write pop() function in a file but I am really stuck.
It looks like it is asking to delete the top element of the stack and returns a Bookmark pointer. Please, help!!

I am showing the header which explains what needs to be done.

#include "Bookmark.h"


class ArrayStack {
	Bookmark **elements;//stores the array of Bookmark pointers
	int numElements, capacity;
	
	public:
	    //initializes an empty stack with capacity maxCapacity.  The array initialized 
		//holds pointers to Bookmarks.
		ArrayStack(int maxCapacity);


		//Deallocates the Stack and all of the Bookmarks in the Stack.
		~ArrayStack();


		//Preconditions: newEl is a pointer to a Bookmark object
		//Postconditions: newEl gets pushed on the stack if it does not exceed the capacity
    	//Returns: true if pushed and false otherwise
		bool push(Bookmark *newEl);


		//Postconditions: the Stack has the top element popped if the stack is non-empty
		//Returns: a pointer to the Bookmark at the top of the stack if it exists and NULL
		// if the Stack is empty.
		Bookmark *pop();
			

		//Returns: a pointer to the Bookmark at the top of the stack if it exists and NULL
		// if the Stack is empty.		
		Bookmark *top();


		//Returns: the number Bookmarks in the stack
		int getNumElements();
		

		//Postconditions: the Stack remains unchanged
		//Returns: true if the Stack is empty and false otherwise		
		bool isEmpty();


		//Postconditions: the Stack remains unchanged
		//Returns: true if the Stack is full and false otherwise
		bool isFull();
};

Code for Bookmark.h:

#include <cstdlib>
#include <cstring>
#include <cstdio>

class Bookmark{
    char *address;//stores the address for the website
	char *title; //stores the title for the website
	int visits; //stores the number of times this page gets visited.
	
 public:

    //initializes a Bookmark with a *copy* of newAddress and newTitle dynamically allocated as webAddress
	//and title, with 0 for visits
    Bookmark(char *newAddress, char *newTitle);

    //Preconditions: newName is a reference to a string
    //Postconditions: changes the address of the Bookmark to be a copy of newName dynamically allocated
	void setAddress(char *newName);


    //Postconditions: Bookmark remains unchanged
	//Returns: a reference to the string containing the address of the Bookmark
	char *getAddress();
	
	//Preconditions: newName is a reference to a string
	//Postconditions: changes the title of the Bookmark to be a copy of newName dynamically allocated
	void setTitle(char *newName);


	//Postconditions: Bookmark remains unchanged
	//Returns: a reference to the string containing the title of the Bookmark
	char *getTitle();
			
		
    //Postconditions: the number of visits has been increased by one.
	void increaseVisits();

    //Returns: the number of times the page is visited
	int getVisits();

	//Deallocates all memory associated with the Bookmark.
    ~Bookmark();	
};

[VernonDozier]

I would imagine that the pop() function would be one of the last if not THE last function you'd write. You can't write it without writing top() first. getNumElements() would presumably be written first, followed by isEmpty(), isFull(), and push(), followed by top(). When all that's written and works, you write pop(). pop() will return top(). It will also delete the top element and make the new top element what used to be the second element. Look at the push() code and sort of reverse it.

[codeyy]

Hi! Thanks for the reply.
I cannot still figure out a simple, working way to write pop().
I have written this but I doubt it will work.

//Postconditions: the Stack has the top element popped if the stack is non-empty
//Returns: a pointer to the Bookmark at the top of the stack if it exists and NULL
// if the Stack is empty.
Bookmark *ArrayStack::pop() {
	if(numElements>=0){
		int cap=capacity;
		newNumEl=numElements-1;
		ArrayStack *shorterStack;   //Note the asterisk. It is a pointer to ArrayStack.
		shorterStack=new ArrayStack(cap);
		for(int i=0;i<newNumEl;i++){
			shorterStack.elements[i]=elements[i];
		}
		shorterStack.numElements=newNumEl;
		delete(elements);
		if(shorterStack.numElements>0){
			return shorterStack.elements[newNumEl-1]; //returns a pointer to the top of the stack
		}
		else {
			return NULL;
		}
	}
	return NULL;
}

[VernonDozier]

Lines 8 and 9. You should not be creating a "new" anything. You already have your object. You are changing it. The words "new" and "delete" should not occur anywhere in this function. "new" is in the constructor. "delete" is in the destructor. As mentioned, this should be the last function you write.

1. Check if there is anything to pop.
2. If there is, create a temporary pointer to it so you don't lose it. You'll need it later for the return.
3. Move everything up one in the array.
4. Adjust the number of elements in the stack.

[VernonDozier]

Actually, scratch numbers 2 and 3. This is a stack. The whole point is that you never have to do any shifting at all.

[codeyy]

Actually, scratch numbers 2 and 3. This is a stack. The whole point is that you never have to do any shifting at all.

Hi!

Thanks for the reply.
Somehow my ArrayStack.cc compiled correctly (after initializing newNumEl as int). But any way, I did not understand what exactly you mean when you say scratch Steps 2 and 3 because then there is nothing left to do!

Please, help.

[VernonDozier]

There's hardly anything to this function. Might be easiest just to give it you.

Bookmark* ArrayStack::pop() 
{
    if(numElements==0)
    {
        return NULL;
    }
    numElements--;
    return elements[numElements];
}

That's it!

[codeyy]

Thanks for the code but I don't understand how will this delete the top element of the Stack. I think pop() is supposed to remove the top element. So, if the top element does not get removed, then the next time we want to pop() the stack, we will get the same result.

Am I wrong? Please clarify.

[codeyy]

I think I understand it now. Once numElements is decreased by one, the Stack is shortened automatically.

[Narue]

With that implementation, beware the next push, because it will overwrite the object pointed to by the previous pop. Mysterious data corruption is an insidious bug.

[codeyy]

With that implementation, beware the next push, because it will overwrite the object pointed to by the previous pop. Mysterious data corruption is an insidious bug.

Whose implementation?
Mine or the other simple-looking one?

[Narue]

I was referring to the working version posted by Vernon. Yours was too broken to consider subtle bugs in the interface. ;)

[codeyy]

I was referring to the working version posted by Vernon. Yours was too broken to consider subtle bugs in the interface. ;)

//Postconditions: the Stack has the top element popped if the stack is non-empty
//Returns: a pointer to the Bookmark at the top of the stack if it exists and NULL
// if the Stack is empty.
Bookmark *ArrayStack::pop() {
	if(numElements>=0){
		int cap=capacity;
		int newNumEl=numElements-1;
		ArrayStack *shorterStack;   //Note the asterisk. It is a pointer to ArrayStack.
		shorterStack=new ArrayStack(cap);
		for(int i=0;i<newNumEl;i++){
			shorterStack.elements[i]=elements[i];
		}
		shorterStack.numElements=newNumEl;
		delete(elements);
		if(shorterStack.numElements>0){
			return shorterStack.elements[newNumEl-1]; //returns a pointer to the top of the stack
		}
		else {
			return NULL;
		}
	}
	return NULL;
}

[VernonDozier]

>> I was referring to the working version posted by Vernon.

Not sure I'm following. Here's a quick and dirty implementation. Ignore the shallow copy in the Bookmark constructor because (I think) it's irrelevant to what you're saying. I'm not seeing anything overwritten?

#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <iostream>

class Bookmark {
    char *address; //stores the address for the website
    char *title; //stores the title for the website
    int visits; //stores the number of times this page gets visited.

public:

    //initializes a Bookmark with a *copy* of newAddress and newTitle dynamically allocated as webAddress
    //and title, with 0 for visits

    Bookmark(char *newAddress, char *newTitle) {
        address = newAddress;
        title = newTitle;
        visits = 0;
    }

    void print() {
        std::cout << address << "\t" << title << "\t" << visits << "\n";
    }

    //Preconditions: newName is a reference to a string
    //Postconditions: changes the address of the Bookmark to be a copy of newName dynamically allocated
    void setAddress(char *newName);


    //Postconditions: Bookmark remains unchanged
    //Returns: a reference to the string containing the address of the Bookmark
    char *getAddress();

    //Preconditions: newName is a reference to a string
    //Postconditions: changes the title of the Bookmark to be a copy of newName dynamically allocated
    void setTitle(char *newName);


    //Postconditions: Bookmark remains unchanged
    //Returns: a reference to the string containing the title of the Bookmark
    char *getTitle();


    //Postconditions: the number of visits has been increased by one.
    void increaseVisits();

    //Returns: the number of times the page is visited
    int getVisits();

    //Deallocates all memory associated with the Bookmark.

    ~Bookmark() {

    }
};

class ArrayStack {
    Bookmark **elements; //stores the array of Bookmark pointers
    int numElements, capacity;

public:
    //initializes an empty stack with capacity maxCapacity.  The array initialized
    //holds pointers to Bookmarks.

    ArrayStack(int maxCapacity) {
        capacity = maxCapacity;
        elements = new Bookmark*[capacity];
        numElements = 0;
    }


    //Deallocates the Stack and all of the Bookmarks in the Stack.

    ~ArrayStack() {
        delete []elements;
    }


    //Preconditions: newEl is a pointer to a Bookmark object
    //Postconditions: newEl gets pushed on the stack if it does not exceed the capacity
    //Returns: true if pushed and false otherwise

    bool push(Bookmark *newEl) {
        if (numElements < capacity) {
            elements[numElements] = newEl;
            numElements++;
            return true;
        }

        return false;
    }


    //Postconditions: the Stack has the top element popped if the stack is non-empty
    //Returns: a pointer to the Bookmark at the top of the stack if it exists and NULL
    // if the Stack is empty.

    Bookmark* ArrayStack::pop() {
        if (numElements == 0) {
            return NULL;
        }
        numElements--;
        return elements[numElements];
    }

    //Returns: a pointer to the Bookmark at the top of the stack if it exists and NULL
    // if the Stack is empty.
    Bookmark *top();


    //Returns: the number Bookmarks in the stack
    int getNumElements();


    //Postconditions: the Stack remains unchanged
    //Returns: true if the Stack is empty and false otherwise
    bool isEmpty();


    //Postconditions: the Stack remains unchanged
    //Returns: true if the Stack is full and false otherwise
    bool isFull();
};

int main(int argc, char** argv) {
    char* address[2] = {"Add1", "Add2"};
    char* title[2] = {"Title1", "Title2"};

    Bookmark* elem1 = new Bookmark(address[0], title[0]);
    Bookmark* elem2 = new Bookmark(address[1], title[1]);

    elem1->print();
    elem2->print();
    ArrayStack* as = new ArrayStack(2);
    as->push(elem1);
    as->pop();
    as->push(elem2);
    elem1->print();
    elem2->print();

    delete elem1;
    delete elem2;
    delete as;
    std::cin.get();
    return (EXIT_SUCCESS);
}

It's the OP's code, most of which is left undone, but enough filled in by me to do a test. Display is...

Add1	Title1	0
Add2	Title2	0
Add1	Title1	0
Add2	Title2	0

[VernonDozier]

//Postconditions: the Stack has the top element popped if the stack is non-empty
//Returns: a pointer to the Bookmark at the top of the stack if it exists and NULL
// if the Stack is empty.
Bookmark *ArrayStack::pop() {
	if(numElements>=0){
		int cap=capacity;
		int newNumEl=numElements-1;
		ArrayStack *shorterStack;   //Note the asterisk. It is a pointer to ArrayStack.
		shorterStack=new ArrayStack(cap);
		for(int i=0;i<newNumEl;i++){
			shorterStack.elements[i]=elements[i];
		}
		shorterStack.numElements=newNumEl;
		delete(elements);
		if(shorterStack.numElements>0){
			return shorterStack.elements[newNumEl-1]; //returns a pointer to the top of the stack
		}
		else {
			return NULL;
		}
	}
	return NULL;
}

I'll refrain from offering more advice on the right way of doing it until someone weighs in on whether I indeed have a bug in my solution. I'll just comment on some of the problems of yours.

1. Don't create a new ArrayStack. It's a local variable that immediately goes out of scope. It thus can never be accessed.
2. The "this" object, on the other hand, remains. Yet you delete elements[] on line 14. Next time you try to access elements[], you're looking at a segmentation fault.
3. I assume you mean > 0 rather than >= 0 on line 5? If that's not a typo, make numElements 0 and notice what happens on line 7.
4. Lines 15 - 20 -- Make sure you are comparing correctly and are not one off on the indexes and numElements comparison.

Anyway, again, I'll put my earlier solution in limbo until someone weighs in again, but for sure do not create a new ArrayStack.

[Narue]

My mistake, I misread the stack as containing objects rather than pointers.