Thread: Making Stack via Dynamic Array

  1. #1
    Registered User
    Join Date
    Oct 2011
    Posts
    15

    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
    };

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Oct 2011
    Posts
    15
    I'm trying to take this non-dynamic array and make it dynamic.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Well, since you say you know how dynamic arrays work, what's missing?

    Also, have you considered using std::vector or std::deque?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Oct 2011
    Posts
    15
    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?

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    Oct 2011
    Posts
    15
    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.

  8. #8
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    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 Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Registered User
    Join Date
    Oct 2011
    Posts
    15
    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?
    Last edited by Linell Bonnette; 10-24-2011 at 05:31 PM.

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Dynamic array in Stack ?
    By janaka in forum C++ Programming
    Replies: 2
    Last Post: 07-30-2009, 12:19 AM
  2. Making an array dynamic
    By madmax2006 in forum C Programming
    Replies: 7
    Last Post: 02-10-2009, 06:50 AM
  3. Dynamic stack?
    By vikernes in forum C++ Programming
    Replies: 6
    Last Post: 06-19-2007, 01:31 PM
  4. help with making a dynamic array sized global stuct
    By Josh Kasten in forum C++ Programming
    Replies: 3
    Last Post: 01-05-2003, 06:23 AM
  5. Making a Stack using Pointers
    By Unregistered in forum C Programming
    Replies: 9
    Last Post: 07-27-2002, 11:51 AM