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

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

Notice that there are two pointers, front and back

Linked List based Queue - C++ Details

Implementation

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.