Making Stack via Dynamic Array

I can't wrap my head around how I would implement the following code using a dynamic array. Two stacks from this class will be used to make a queue class.

I know how dynamic arrays work, but they're not exactly my strong suit. How would I make them work for this?

Code:

---

class stack
{
public:
    static const int CAPACITY = 30;
        // Constructor
    stack () { used = 0; }
        // Modification Member Functions
    void push(const int& entry);
    void pop();
        // Constant member functions
    bool empty() const { return (used == 0);}
    int size() const { return used; }
    int top() const;
private:
    int data[CAPACITY]; // Partially filled array
    int used;            // How much of the array is being used
};

---

If it is really supposed to be a dynamic array, then these lines don't make sense:

Code:

---

static const int CAPACITY = 30;

---

Code:

---

int data[CAPACITY]; // Partially filled array

---

I'm trying to take this non-dynamic array and make it dynamic.

Well, since you say you know how dynamic arrays work, what's missing?

Also, have you considered using std::vector or std::deque?

We're not allowed to use vector and deque.

I'm missing a dynamic array, mostly. I need to have it somehow allocated at run-time. My main problem is that I'm not sure how I can pass the capacity all the way back to the stack class. Maybe I could ask for input, then have say q1 (representing a queue) q1->set_capacity();

set_capacity() could then call a function from the stack class that would have capacity = new int [n].

That seems rather backwards though. Is there a better way?

Quote:

---

Originally Posted by Linell Bonnette

My main problem is that I'm not sure how I can pass the capacity all the way back to the stack class.

---

A general technique:

• Start with an initial capacity to create the dynamic array.
• When a push happens, check if the resulting size will exceed the capacity. If so, expand the capacity by some factor, e.g., double it. Remember to copy over the elements from the old dynamic array to the new dynamic array, and then destroy the old dynamic array.
• Implement or disable the copy constructor and copy assignment operator.
• Implement the destructor.

So I would start off with the something like

Code:

---

int data = new int [CAPACITY]

---

, right? After that, during the push

Code:

---

(if q1.queue_size() >= s2->CAPACITY) {resize_capacity(2);}

---

, or something along those lines? Except with the elements copied.

Obviously you must never allow the size to exceed the capacity.
If a push will make the size exceed the capacity, then you need to expand the capacity.
Also, I imagine resize_capacity would look something like resize_capacity(Capacity * 2);

Quote:

---

Originally Posted by Linell Bonnette

So I would start off with the something like

Code:

---

int data = new int [CAPACITY]

---

, right?

---

Yes, something like that, except that CAPACITY would be a non-static non-const member variable, so it would conventionally be named in lower case, not upper case. data would likewise be a member variable of type int*, not a local variable.

Quote:

---

Originally Posted by Linell Bonnette

After that, during the push

Code:

---

(if q1.queue_size() >= s2->CAPACITY) {resize_capacity(2);}

---

, or something along those lines?

---

Yes, something like that, except that I am curious as to what you think q1 is supposed to be, and why there is a member function named queue_size().

If your answer is that "two stacks from this class will be used to make a queue class", then I must point out to you that you are currently writing a stack class, not a queue class, so thinking about a queue class will only produce a class that neither models a stack nor a queue.

I was thinking that I would have to get to the stack class from main. Would I be able to just have that done inside of the stack class?

I've changed the code to be

Code:

---

class stack
{
public:
        // Constructor
    stack () { used = 0; capacity = 30; data = new int [capacity];}
        // Modification Member Functions
    void push(const int& entry);
    void pop();
        // Constant member functions
    bool empty() const { return (used == 0);}
    int size() const { return used; }
    int top() const;
private:
    int capacity;
    int * data;            // Partially filled array
    int used;            // How much of the array is being used
};

---

This compiles just fine, and seems to run fine for some small values. However, if I try to push a large amount (say 400), then it gives me a bad access error. What is the problem?

Quote:

---

Originally Posted by Linell Bonnette

This compiles just fine, and seems to run fine for some small values. However, if I try to push a large amount (say 400), then it gives me a bad access error. What is the problem?

---

Since you did not show the code for the push member function, I can only tell you this: the problem is that you have a bug in your code.