Stack
template <class item_type, int max_size>
class stack
{
stack();
boolean is_empty();
boolean is_full();
void push(item_type new_item);
item_type top();
void pop();
~stack();
};
- Stack is really a special type of list. Since we have already
written the list type, let us use it to define stack operations.
- Inheritance allows us to reuse some of the list code.
- Three important features of Object Oriented Programming
- Encapsulation
- Inheritance
- Polymorphism
- We have already looked at encapsulation.
- Encapsulating data and function members in the type definition.
- The old records/structs allowed only collection of data
members
- Because a data type is more than its data members. In fact,
data type has little to do with the data members. It is not what
it has, it is what it does that is important.
- Inheritance: Allows us to derive special types from more
general types.
- The derived types are also called children.
- Let us that stack will be derived from the list
template <class item_type, int max_size>
class stack : public list<item_type,max_size>
{
void push(item_type new_item);
item_type top();
void pop();
};
- Automatically, all the data members and function members
of the list are also data and function members of the stack
- stack inherits everything that list has
- stack needs a few additional operations, namely, push,
pop, top. So we added them in the type definition above.
- We will assume that the top of the stack corresponds to
the first item.
-
template <class item_type, int max_size>
class stack : public list<item_type,max_size>
{
public:
void push(item_type new_item)
{insert_before(new_item);}
item_type top()
{return current_item();}
void pop()
{erase();}
};
- Time requirement for push and pop is linear. Time requirement
for the top is constant
- If we make the last element in the list to be the top of
the stack
template <class item_type, int max_size>
class stack : public list<item_type,max_size>
{
public:
void push(item_type new_item)
{
if(is_empty()) insert_before(new_item);
else insert_after(new_item);
}
item_type top()
{return current_item();}
void pop()
{erase();cursor--;}
};
- Now we don't need to shift all the elements in the stack.
So all operations are constant time.
- There is only one problem, the underlying array size is
fixed to the maximum possible size. If we guessed it wrong, our
stack will be full and useless in some cases. If the size requirements
fluctuate from say 10 to 200, then we will be wasting a lot of
space just to take care of the worst case situation.