Linked List Based Implementation of Stack and Queue

Why different implementations

• The way the data structure is implemented is a measure of its efficiency (time and space)
  
• It is important to see different alternatives
  
• So far we have discussed array based implementation (vector). What if we use second class arrays?
  

Objectives:
Discuss linked list based implementation of stack and queue.
Compare and contrast two implementations

Linked List based Stack

• Stack is LIFO data structure
  
  
  
  
  
  
  
  
  
• Linked list is a collection of nodes where each node has a data element and a pointer to the next element in the list.
  
  

Linked List based Stack- basic concepts

• Stack we push into and pop from the top of the stack.
  
• Therefore a special pointer “toOftheStack” which is pointing to the top of the stack is created.
  
• Intially toOftheStack is null.
  
• Try following operations
  
• push (a), push(b), push(c)
  
• pop()
  

Linked List based Stack- C++ Details
A Node: (figure 16.19)

struct ListNode
{
Object element;
ListNode *next;
ListNode ( const Object & theElement, ListNode * n = NULL ) : element( theElement ), next( n ) { }

};

Linked List based Stack- C++ Details
Template
template <class Object> class Stack {
public:
Stack( );
Stack( const Stack & rhs );
~Stack( ); bool isEmpty( ) const;
const Object & top( ) const;
void makeEmpty( );
void pop( );
void push( const Object & x );
Object topAndPop( );
const Stack & operator=( const Stack & rhs );

private:
struct ListNode { Object element; ListNode *next; ListNode( const Object & theElement, ListNode * n = NULL ) : element( theElement ), next( n ) { } };

ListNode *topOfStack; };

Linked List based Stack- C++ Details
Implementation
Stacklist.cpp
push, pop, top, makeEmpty and = operator

Linked List based Queue

• Queue if FIFO data structure
• Implementation is very similar to stack. Here, both from and back of the data structure need pointers.

Linked List based Queue- basic concepts

• Queue, enqueue into the front of the stack. Dequeue from the back of the stack
• Therefore two special pointers “front,” and “back,” are created.
• Initially both both front and back are null.
• Try following operations
• enqueue (a), enqueue(b), enqueue(c)
• dequeue()

Linked List based Queue - C++ Details
A Node:

struct ListNode {
Object element;
ListNode *next;
ListNode( const Object & theElement, ListNode * n = NULL ) : element( theElement ), next( n )
{ }
};

Linked List based Queue - C++ Details
Template
Queuelist.h
Notice that there are two pointers, front and back

Linked List based Queue - C++ Details
Implementation
Queuelist.cpp
Enqueue, dequeue, copy constructure and = operator

Array base vs. Linked list based Implementation

• For large size stacks and queue specially the size is not known linked list is better.
• For memory scare devices such as small handheld devices, linked list may perform better.