"isFull" function help

[Cross213]

I would like to know how the isFull() function works for a Stack and a Queue, but by implementing the Stack as a dynamic array(without a predefined size) and implementing the Queue as a linked list.

[L7Sqr]

In general, determining if something is full requires you to have a fixed size of storage. Once what you are storing consumes the available storage the container is full.
Check the count of how many things have been inserted into your stack against the size of the internal container of your stack. If the two are equal then the container is full.

[Cross213]

Yes I understand that concept of isFull, but there is also another way to do it where you set a certain amount of memory for array and once that amount has been reached, your stack is then deemed to be full. This way is used so that your array can grow and shrink at will, without the restrictions of a fixed size. In other words, size = 0 to begin with and incremented and decremented at will.

[Fbody]

The size of an array (in bytes) is determined by the size of a single item in the array and the number of slots the array has. If you have an array of int that has 4 elements, the size of the array is [TEX](sizeof(int) * 4) = (4 * 4) = 16 bytes[/TEX] (assuming 32-bit ints). But, you are better off basing your comparison on capacity (how many can it hold?) vs. count (how many are in it now?), it's just easier.

The concept is basically the same as what L7Sqr described, you just react to the situation differently. Instead of throwing an error back in the user's face, you quietly re-size the internal container, copy the existing data, then go about your business.

To make it work with a dynamic capacity, you'll have to keep track of a "capacity" value and a "used" value. Once the used value == the capacity value, you re-allocate the container with a higher capacity and set the capacity value to whatever that new value is. That way, the state returns to used != capacity.

I suggest you study the std::vector class. It works in much the same way as the behavior you describe.

[L7Sqr]

In other words, size = 0 to begin with and incremented and decremented at will.

I'm not sure I understand your problem. If you've got a Stack, implemented as follows:

template< typename T >
struct Stack {
   T buffer_[SIZE];
   int nelements_;
   //...
};

Then when nelements_ == SIZE your Stack is full. What you do at that point (resize vs. fail to accept new elements) is entirely up to you.

In the case of a linked list, the choice is even more arbitrary since there is no 'container' that limits how many things you can store. You can set an arbitrary limit on the number of things that can be placed in the list and when you get to that number set the Queue to be full otherwise you just keep managing more nodes in the list as necessary.

If you allow a container to grow or shrink at will then there is no 'full' - there is only 'needs to be resized'. I'm not sure of what you are asking, I guess.

[Cross213]

The thing is I'm kinda not allowed to have a fixed size so I'm looking for an alternative, but I get what you guys and are saying and thanx for the help, I at least learnt something

[Fbody]

You don't need a "fixed" size. You use the language's dynamic allocation tools to create objects "on-the-fly".

At some point you need to have a known size, it doesn't necessarily mean that it's "fixed", whether that's provided by the user or by your code is up to you. You just need to organize your code appropriately for the situation.

[L7Sqr]

So you are looking for an internal flag that represents when it is time to resize the container?

struct Stack {
   int * buff_; // the internal storage
   int cap_, nelm_; // current capacity and current count of items

   /*
    * Initially, buff_ is NULL and cap_ and nelm_ are set to 0
    */

   // ...
   void push (int value) {
      if (nelm_ >= cap_) {
         // need to resize
      } else {
         buff_[nelm_] = value;
         ++nelm_;
      }
   }
   // ... 
};

If you need to expose that property just provide a bool isFull (); method to the class.

In terms of the Queue, where you are using a linked list it might look something like

struct Queue {
   List list;
   int nelm_; // current number of elements, initially 0
   int cap_; // maximum # of elements - set this how you like

   // ...
   void push (int value) {
      if (nelm_ >= cap_) {
         // Full - what do you expect to do here?
      } else {
         list->append (value);
      }
   }
   // ...
};

Like I said, I'm not sure what 'full' means for a linked list - lists dont get full.

Does what I describe above explain your assignment/problem accurately? If not, what else are you trying to achieve?

[Cross213]

This is fine yes thanx alot