Transcript Implementing a Stack as a Linked Structure

Stack and Queues using
Linked Structures
Kruse and Ryba Ch 4
Implementing stacks using arrays
• Simple implementation
• The size of the stack must be determined
when a stack object is declared
Space is wasted if we use less elements
•
• We cannot "push" more elements than the
array can hold
Dynamic allocation of each
stack element
• Allocate memory for
each new element
dynamically
ItemType* itemPtr;
...
itemPtr = new ItemType;
*itemPtr = newItem;
Dynamic allocation of each
stack element (cont.)
• How should we preserve the order of the
stack elements?
Chaining the stack elements
together
Chaining the stack elements
together (cont.)
• Each node in the stack should contain two
parts:
– info: the user's data
– next: the address of the next element in the
stack
Node Type
template<class ItemType>
struct NodeType {
ItemType info;
NodeType* next;
};
First and last stack elements
• We need a data member to store the pointer
to the top of the stack
• The next element of the last node should
contain the value NULL
Stack class specification
// forward declaration of NodeType (like function prototype)
template<class ItemType>
struct NodeType;
template<class ItemType>
class StackType {
public:
StackType();
~StackType();
void MakeEmpty();
bool IsEmpty() const;
bool IsFull() const;
void Push(ItemType);
void Pop(ItemType&);
private:
NodeType<ItemType>* topPtr;
};
Pushing on a
non-empty
stack
Pushing on a non-empty stack
(cont.)
• The order of changing the pointers is very
important !!
Pushing on an empty stack
Function Push
template <class ItemType>
void StackType<ItemType>::Push(ItemType
item)
{
NodeType<ItemType>* location;
location = new NodeType<ItemType>;
location->info = newItem;
location->next = topPtr;
topPtr = location;
}
Popping the top element
Popping the top
element
(cont.)
Need to use a
temporary
pointer
Function Pop
template <class ItemType>
void StackType<ItemType>::Pop(ItemType& item)
{
NodeType<ItemType>* tempPtr;
item = topPtr->info;
tempPtr = topPtr;
topPtr = topPtr->next;
delete tempPtr;
}
Popping the last element on the stack
Other Stack functions
template<class ItemType>
StackType<ItemType>::StackType()
{
topPtr = NULL;
}
template<class ItemType>
void StackType<ItemType>::MakeEmpty()
{
NodeType<ItemType>* tempPtr;
while(topPtr != NULL) {
tempPtr = topPtr;
topPtr = topPtr->next;
delete tempPtr;
}
}
Other Stack functions (cont.)
template<class ItemType>
bool StackType<ItemType>::IsEmpty() const
{
return(topPtr == NULL);
}
template<class ItemType>
bool StackType<ItemType>::IsFull() const
{
NodeType<ItemType>* location;
location = new NodeType<ItemType>;
if(location == NULL)
template<class ItemType>
return true;
StackType<ItemType>::~StackType()
else {
{
delete location;
MakeEmpty();
return false;
}
}
}
Copy Constructors for stacks
• Suppose we want to make a copy of a stack, will
the following work?
template<class ItemType>
void StackType(StackType<ItemType> oldStack,
StackType<ItemType>& copy)
{
StackType<ItemType> tempStack;
while(!tempStack.IsEmpty()) {
ItemType item;
tempStack.Pop(item);
copy.Push(item);
while(!oldStack.IsEmpty()) {
}
oldStack.Pop(item);
}
tempStack.Push(item);
}
Copy Constructors (cont.)
• Shallow Copy: an object is copied to another
•
object without copying any pointed-to data
Deep Copy: makes copies of any pointed-to
data
When do you need a copy constructor?
(1) When parameters are passed by value
(2) Return the value of a function
(return thisStack;)
(3) Initializing a variable in a declaration
(StackType<int> myStack=yourStack;)
Copy constructor for stacks
template<class ItemType>
Stack Type<ItemType>::StackType(const StackType<ItemType>&
anotherStack)
{
NodeType<ItemType>* ptr1;
NodeType<ItemType>* ptr2;
if(anotherStack.topPtr == NULL)
topPtr = NULL;
else {
topPtr = new NodeType<ItemType>;
topPtr->info = anotherStack.topPtr->info;
ptr1 = anotherStack.topPtr->next;
ptr2 = topPtr;
while(ptr1 !=NULL) {
ptr2->next = new NodeType<ItemType>;
ptr2 = ptr2->next;
ptr2->info = ptr1->info;
ptr1 = ptr1->next;
}
ptr2->next = NULL;
}
}
Alternatively,
copy one stack
to another
using the
assignment
operator (you
need to
overload it
though!!)
Comparing stack implementations
Big-O Comparison of Stack Operations
Operation
Array
Linked
Implementation Implementation
Class constructor
MakeEmpty
IsFull
IsEmpty
Push
Pop
Destructor
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
O(N)
O(1)
O(1)
O(1)
O(1)
O(N)
Implementing queues using
arrays
• Simple implementation
• The size of the queue must be determined
when a stack object is declared
Space is wasted if we use less elements
•
• We cannot "enqueue" more elements than
the array can hold
Implementing queues using
linked lists
• Allocate memory for each new element
dynamically
Link the queue elements together
•
• Use two pointers, qFront and qRear, to
mark the front and rear of the queue
Queue class specification
// forward declaration of NodeType (like function prototype)
template<class ItemType>
struct NodeType;
template<class ItemType>
class QueueType {
public:
QueueType();
~QueueType();
void MakeEmpty();
bool IsEmpty() const;
bool IsFull() const;
void Enqueue(ItemType);
void Dequeue(ItemType&);
private:
NodeType<ItemType>* qFront;
NodeType<ItemType>* qRear;
};
Enqueuing (non-empty queue)
Enqueuing (empty queue)
• We need to make qFront point to the new
node also
qFront = NULL
New Node
qRear = NULL
newNode
Function Enqueue
template <class ItemType>
void QueueType<ItemType>::Enqueue(ItemType
newItem)
{
NodeType<ItemType>* newNode;
newNode = new NodeType<ItemType>;
newNode->info = newItem;
newNode->next = NULL;
if(qRear == NULL)
qFront = newNode;
else
qRear->next = newNode;
qRear = newNode;
}
Dequeueing (the queue contains
more than one element)
Dequeueing (the queue contains
only one element)
• We need to reset qRear to NULL also
qFront
After dequeue:
Node
qRear
qFront = NULL
qRear = NULL
Function Dequeue
template <class ItemType>
void QueueType<ItemType>::Dequeue(ItemType& item)
{
NodeType<ItemType>* tempPtr;
tempPtr = qFront;
item = qFront->info;
qFront = qFront->next;
if(qFront == NULL)
qRear = NULL;
delete tempPtr;
}
qRear, qFront revisited
• The relative positions of qFront and qRear
are important!
Other Queue functions
template<class ItemType>
void QueueType<ItemType>::MakeEmpty()
{
NodeType<ItemType>* tempPtr;
while(qFront != NULL) {
tempPtr = qFront;
qFront = qFront->next;
delete tempPtr;
}
qRear=NULL;
}
Other Queue functions (cont.)
template<class ItemType>
bool QueueType<ItemType>::IsEmpty() const
{
return(qFront == NULL);
}
template<class ItemType>
bool QueueType<ItemType>::IsFull() const
{
NodeType<ItemType>* ptr;
ptr = new NodeType<ItemType>;
if(ptr == NULL)
return true;
else {
delete ptr;
return false;
}
}
Other Queue functions (cont.)
template<class ItemType>
QueueType<ItemType>::~QueueType()
{
MakeEmpty();
}
A circular linked queue design
Comparing queue implementations
• Memory requirements
– Array-based implementation
• Assume a queue (size: 100) of strings (80 bytes
each)
• Assume indices take 2 bytes
• Total memory: (80 bytes x 101 slots) + (2 bytes x 2
indexes) = 8084 bytes
– Linked-list-based implementation
• Assume pointers take 4 bytes
• Total memory per node: 80 bytes + 4 bytes = 84
bytes
Comparing
queue
implementations
(cont.)
Comparing queue implementations
• Memory requirements
(cont.)
– Array-based implementation
• Assume a queue (size: 100) of short integers
(2 bytes each)
• Assume indices take 2 bytes
• Total memory: (2 bytes x 101 slots) + (2 bytes x 2
indexes) = 206 bytes
– Linked-list-based implementation
• Assume pointers take 4 bytes
• Total memory per node: 2 bytes + 4 bytes = 6 bytes
Comparing
queue
implementations
(cont.)
Comparing queue implementations
Big-O Comparison of Queue Operations
Operation
Array
Linked
Implementation Implementation
Class constructor
MakeEmpty
IsFull
IsEmpty
Enqueue
Dequeue
Destructor
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
O(N)
O(1)
O(1)
O(1)
O(1)
O(N)