A stack ADT implemented using pointers
We are going to implement the stack ADT using a linked list.
17 21
top
In the above example, there is a pointer called top that points to a node containing the int 21. The node that contains 21 points to a node containing the int 17.
This stack is a stack of int values with 17 at the bottom of the stack, and 21 at the top of the stack. The 17 was pushed on the stack first, then 21 was pushed on the stack.
Each node will have two data members, called item and next.
item stores an int;
next points to a node.
struct
Node
{
int item;
Node* next;
};
Node
top is a Node* pointing to the node that contains the topmost item on the stack .
An empty stack has no nodes. For an empty stack, top will contain a NULL pointer value, indicating that it does not point to any node. In diagrams, we draw the NULL value with a diagonal line from the to bottom left to the top right.
top
After pushing 17 on an empty stack, we obtain:
17
top
And if we now push 21, we obtain a stack with two items. The 17 has been pushed down, and 21 has been pushed on top of the stack.
17 21
top
The stack ADT has an explicit default constructor, an explicit copy constructor, an explicit destructor, methods for pushing and popping the stack, a method for viewing the top item, and methods for determining if a stack is empty or full.
class Stack {
public:
Stack();
Stack( const
Stack& srcStack );
~ Stack();
void Push( /* in
*/ int newItem );
int
Top() const;
int
Pop();
bool
IsEmpty() const;
bool
IsFull() const;
private:
struct
Node
{
int item;
Node* next;
};
Node* top;
};
|
This is the same public stack interface (except for the
addition of the explicit copy constructor and explicit destructor) that we
used for the array implementation of the stack ADT. |
Implementation of the
stack constructor
We initialize the stack's top data member to NULL.
top
Stack::Stack()
{
top = NULL;
}
Implementation of void Push( /* in
*/ int newItem )
First, we create a new node to store the new item, then this new node must be inserted immediately in front of the topmost node.
17
top
insert here
Step 1. Create a new node.
Node* newPtr = new
Node;
17
top
newPtr
Step 2. Store the new item in the new node.
newPtr->item = newItem;
17
top
newPtr
Step 3. Link the new node to the topmost node.
newPtr->next = top;
17
top
newPtr
Dotted arrows represent an assignment
(copy) of a value.
Solid
arrows represent
pointers.
Step 4. Link top to the new node.
top = newPtr;
17
top
newPtr
The above code also works when the stack was empty just before the call of Push().
Step 1. Create a new node.
Node* newPtr = new
Node;
top
newPtr
Step 2. Store the new item in the new node.
newPtr->item = newItem;
top
newPtr
Step 3.
newPtr->next = top;
top
21
newPtr
Step 4. Link top to the new node.
top = newPtr;
top
newPtr
The complete code for the Push method is:
void Stack::Push( /* in
*/ int newItem )
{
Node* newPtr =
new Node;
newPtr->item
= newItem;
newPtr->next
= top;
top = newPtr;
}
The new node is created in the heap ( = dynamic store) and continues to exist even after Push() finishes execution.
The newPtr pointer variable is local to the Push method, so it is created when Push() is called; and it is automatically destroyed when Push() finishes execution.
Implementation of int Top( ) const
Top() returns a copy of the topmost item. (The precondition is that the stack contains at least one item, so the implementer does not check that an item exists.)
int
Stack::Top() const
{
return
top->item;
}
Implementation of int Pop( )
Pop removes and returns the topmost item from a stack. The node that stored the topmost item must be returned to the heap. We must "recycle" the memory used by variables that we no longer need.
(The precondition is that the stack contains at least one item.)
17 21
top
remove this node
Step 1. Make a copy of the item in the topmost node. (Later we will return this value to the caller.)
int item = top->item;
Step 2. Declare a local pointer, and point it to the topmost node.
Node* oldPtr
= top;
17 21
top
oldPtr
Step 3. Relink top to the node that is just below the topmost node.
top = top->next;
17 21
top
oldPtr
Step 4. Delete the old topmost node.
delete oldPtr;
17
top
oldPtr
Step
5. Return the saved item.
return item;
The above code also works when the stack contains exactly one item prior to the call of Pop().
21
top
remove this node
Step 1. Make a copy of the item in the topmost node.
int item = top->item;
Step 2. Declare a local pointer, and point it to the topmost node.
Node* oldPtr
= top;
21
top
oldPtr
Step 3.
top = top->next;
21
top
oldPtr
Step 4. Delete the old topmost node.
delete oldPtr;
top
oldPtr
Step
5. Return the saved item.
return item;
The complete code is:
int
Stack::Pop()
{
int item
= top->item;
Node* oldPtr =
top;
top =
top->next;
delete oldPtr;
return item;
}
Implementation of bool IsEmpty( ) const
Return true if the stack is empty; return false if the stack isn't empty.
bool
Stack::IsEmpty() const
{
return ( top ==
NULL );
}
Implementation of bool IsFull( ) const
Return true if the stack is full; return false if the stack isn't full. The stack can only become full if we exhaust the heap. We are going to assume that the heap never becomes empty, so IsFull() always returns false.
bool
Stack::IsFull() const
{
return false;
}
Implementation
of the destructor.
The destructor must return all dynamically allocated memory to the heap.
The algorithm repeatedly pops the stack until it is empty.
Stack::~Stack()
{
Node* oldPtr;
while ( top !=
NULL )
{
oldPtr
= top;
top = top->next;
delete oldPtr;
}
}
Implementation
of the copy constructor.
(The copy constructor is
executed when a stack is initialised
from another stack, or when a stack is passed by value to a function.
void MyFunc( /* in */
Stack );
Stack stack1;
stack1.Push(17);
stack1.Push(21);
Stack stack2 =
stack1; // copy constructor called here
MyFunc(
stack1 ); // copy constructor called
here
...
void MyFunc( /* in */
Stack stack )
{
...
}
The copy constructor has to
clone all of the nodes from the source stack (stack1 in the above
code.)
The algorithm iterates
through the linked list of nodes from the source stack, and for each node,
makes a copy of the node, and appends the copy to the end of the new stack.
Stack::Stack( const
Stack& srcStack )
{
Node* newPtr;
Node* rear = NULL;
top = NULL;
for ( Node* srcPtr = srcStack.top;
srcPtr != NULL;
srcPtr
= srcPtr->next )
{
newPtr
= new Node;
newPtr->item
= srcPtr->item;
newPtr->next
= NULL;
if ( rear ==
NULL )
top = newPtr;
else
rear->next
= newPtr;
rear = newPtr;
}
}