2

my code right now is just a simple stack that has push, pop, and display methods. How can I change my stack so that the size of the stack dynamically resizes based on the number of elements entered? So, for example, if the stack is full, I create a new stack that is twice the size of the original, and copy the data to the new stack.

Thanks.

#include <iostream>
#include <stdexcept>

using namespace std;

class Stack
{
private:
    int *p;
    int top,length;

public:
    Stack(int = 0);
    ~Stack();

    void push(int);
    int pop();
    void display();
};

Stack::Stack(int size)
{
    top=-1;
    length=size;
    while(length <= 0)                //If the stack size is zero, allow user to mention it at runtime
    {
        cout<<"Stack of zero size"<<endl;
        cout<<"Enter a size for stack : ";
        cin >> length;
    }
    p=new int[length];
}

Stack::~Stack()
{
    delete [] p;
}

void Stack::push(int elem)
{
    if(top==(length-1))     //If the top reaches to the maximum stack size
    {
        throw overflow_error("Can't push onto a full stack");
    }
    else
    {
        top++;
        p[top]=elem;
    }
}
int Stack::pop()
{
    if(top==-1)
    {
       throw underflow_error("Can't pop from an empty stack");
    }
    int ret=p[top];
    top--;
    length--;

    return ret;
}

void Stack::display()
{
    for(int i = 0; i <= top; i++)
        cout<<p[i]<<" ";
    cout<<endl;
}

int main()
{
    int len;

    cout<<"Enter a size for stack : ";
    cin >> len;
    Stack s1(len);
    try{
        s1.push(1);
        s1.display();
        s1.push(2);
        s1.push(3);
        s1.push(4);
        s1.push(5);
        s1.display();
        s1.pop();
        s1.display();
        s1.pop();
        s1.display();
        s1.pop();
        s1.display();
        s1.pop();
        s1.display();
        s1.pop();
        s1.display();
    }
    catch(overflow_error){
        cerr<< "Illegal operation. Cannot push onto a full stack.";
        return -1;
    }
    catch(underflow_error){
        cerr<< "Illegal operation. Cannot pop from an empty stack.";
        return -1;
    }


}
user3205160
  • 127
  • 3
  • 4
  • 10

4 Answers4

3
void Stack::push(int elem)
{
    if(top==(length-1))     //If the top reaches to the maximum stack size
    {
        int* newp = new int[length * 2];
        std::memcpy(newp, p, sizeof(int) * length);
        delete[] p;
        p = newp;
        top++;
        p[top]=elem;
        length*=2;
   }
   else
   {
       top++;
       p[top]=elem;
   }

}

BWG
  • 2,238
  • 1
  • 20
  • 32
  • Thanks, did you have a typo at length* = 2? Shouldn't it be length = 2? – user3205160 Jan 18 '14 at 22:21
  • @user3205160 No, I did not have a typo. It is just a compressed version of `length *= 2`, which translates to `length = length * 2`. – BWG Jan 18 '14 at 22:24
  • Thanks for the quick reply. One last thing, does your method work for halving the size of the stack for the pop method? So if the number of elements is less than a quarter of the stack size, I need to create a new stack that is half the size of the original. Then, I proceed with pop(). Thanks. – user3205160 Jan 18 '14 at 22:35
  • @user3205160 Yes, it will work. Feel free to accept my answer also. – BWG Jan 18 '14 at 22:40
  • Would it be something like this? `int Stack::pop() { if (top == 0) { throw underflow_error("Can't pop from an empty stack"); } if (top == (length / 4)) { int* halfPointer = new int[length / 2]; std::memcpy(halfPointer, p, sizeof(int) / length); delete [] p; p = halfPointer; top--; p[top]; length = length * .5; } int ret = p[top]; top--; length--; return ret; } ` – user3205160 Jan 18 '14 at 22:48
  • @user3205160 Yes, something like that would work, except don't `--` length at the end. NO! I was wrong. Don't use realloc, unless you want to rework your whole stack. – BWG Jan 18 '14 at 22:52
  • @user3205160 That is ridiculously basic. How did you manage to right this thing lol? `cout< – BWG Jan 18 '14 at 23:02
  • Sorry. I knew that, it was just the formatting wasn't correct. I'm good now, thanks for everything! – user3205160 Jan 18 '14 at 23:08
1

The stack class in the standard library (std::stack) solves this by delegating to a container class such as std::vector. That's slightly cheating, though.

However, the idea behind std::vector<> is fairly straightforward and reusable. When you hit the maxiumum size, do the following things in order:

  1. Allocate new memory. No big problem if it fails (no data lost)
  2. Copy all existing elements over. Use std::uninitialized_copy not std::copy
  3. Swap the new and old pointer
  4. Delete the old objects
  5. Free the old allocation
MSalters
  • 173,980
  • 10
  • 155
  • 350
0

Instead of throwing the exception overflow_error("Can't push onto a full stack") you can allocate more memory using new and copy the contents to that memory and release the previously allocated memory(memory swapping).

void Stack::push(int elem)
{
   if(top==(length-1))     //If the top reaches to the maximum stack size
   {
    //throw overflow_error("Can't push onto a full stack");
      int *pTemp = new int[length + 10/*value u want to increment*/];
      memcpy(p,pTemp,length);  //for using this include stdlib
      delete[] p;
      p = pTemp;
   }
   top++;
   p[top]=elem;
}
kernel
  • 326
  • 1
  • 3
  • 18
  • 2
    -1 You say something unrelated to OP's question, and essentially tell him to do what he is asking how to do – BWG Jan 17 '14 at 04:32
0

One simple way is to double the stack size each time pushing a new element would overflow the stack. In that instance, you detect the potential overflow and then you would use declare a new int array that is twice the size of the old one and then copy the old array into this new array and reassign the pointer to that new array and delete the old array. The are other more optimal ways, but that is a simplistic way of doing it, you can use up considerably more memory than is necessary to add the new item, but it's a lot faster than reallocating with every new item that would overflow your stack.

JohnDough
  • 11
  • 1