Posts

Showing posts from September, 2018
ScaleFree

DS & A(Stacks - Pointer Based)

Image
In the previous chapter, we talked about Array Based Stacks so continuing our discussion on Stacks, In this chapter, we will see how to implement pointer-based Stacks also known as Linked Stacks.

Visual Representation:


Properties of Linked Stack:

Follows LIFO principle and all the other general properties of a stack.Unlike Array-based stack it's size is not fixed. Its size grows with the addition of new elements.A Linked Stack can have head and tail pointers but it is not mandatory. Stack ADT:

template<typename e> class Stack{public:    //Function to insert a value at the pop of the Stack    virtual bool push(const e& item) = 0;
    //Function to remove top-most Stack value    virtual bool pop(e& item) = 0;
    //Function to Display the stack    virtual void print() const= 0;};
Stack Implementation: Creating the Node: public:template<typename e>class Node{public:    e element;    Link<e>* next;
    Link(e elemValue = 0, Link<e>* nextValue = nullptr)    {      …

DS & A(Stacks - Array Based)

Image
So, we are finally done with List DS for now. And if you made it this far hats off to your determination. Let's start this new chapter with the very same determination. In today's chapter, you will be learning about a new DS called Stack. Now you might be familiar with the word Stack but let us see what it means in the world of DS & A.

Stacks:
Stacks are restricted version of Lists with the following restrictions:Data can only be inserted from the top. Data insertion is referred to as PUSH.Data can only be deleted from the top as well. Data Deletion is referred to as POP.Alternatively, PUSH and POP should always be executed on the same side of the Stack.A Stack follows the LIFOprinciple also known as FILO. The accessible element can be referred to as TOP.Visual Representation:
Stack ADT:

template<typename e> class Stack{public:    //Function to insert a value at the pop of the Stack    virtual bool push(const e& item) = 0;
    //Function to remove top-most Stack value…

DS & A (Lists - Array Lists v/s Pointer Lists)

Image
List Comparison: 

Array List vs Pointer List (Structure Comparison)
Array List
Pointer List


Array List vs Pointer List (Overall Comparison)
Array ListLinked(Pointer) List

Insertion and deletion are easy. Insertion and deletion are complicated as elements cannot be accessed through indices.

Prev and Next element access are easier. Prev and Next element access are comparatively complicated.

The list array must be allocated in advance. The list grows with the increase in the number of elements.

No overhead if all array positions are full. Every element has overheads.

Memory allocated for the Array List must be a contiguous block of memory. Memory allocated for the Linked List doesn't need to be contiguous.

Share on Social Media