Stack Representation using Arrays and Linked List

A stack may be represented in the memory in various ways. There are two main ways: using a one dimensional array and a single linked list. These two powerful data structure are used to represent stack in memory. Each one has it own advantages and disadvantages. In this post your going to learn how arrays and liked list are used to represent stack.

Array (OR) Sequential Representation of Stack:

        An is a linear data structure that sores similar types of data items. Arrays are stores elements in indexed manner. Using arrays to represent stack, first you have to allocate a memory block of sufficient size to accommodate the full capacity of the stack. Then, starting from the first location / index of the memory block, the items of the stack can be stored in a sequential fashion.

ITEMi denotes the ith item in the stack: l and u denotes the index range of the array in use; usually the values of these indices are 1 and size respectively. Top is a pointer to point the portion of the array up to which it is filled with the items of the stack. with this representations, the following two conditions can be stated:

Stack is empty: Top<=1
Stack is full: Top>=u.
Stack size: u+l-1

Advantages:

• Easy to implement
• Random access is easier
• suitable when the number of elements are predefined or already known.

Disadvantages:

• Inserting and deleting elements at and from random position requires shifting of preceding and succeeding elements.
• Size of array is fixed so the elements beyond the size cannot be added.
• Larger array may lead to high memory wastage, if we add only few elements in it.

Linked List Representation of Stack

Although array representation of stacks is very easy and convenient but it allows the representation of only fixed sized stack. In several applications, the size of the stack may vary during program execution. An obvious solution to this problem is to represent a stack using a linked list. A single linked list structure is sufficient to represent any stack. Here, DATA filed is for the ITEM, and the LINK filed is, as usual, to point to the next ITEM.

 In the liked list representation, the first node on the list is the current item that the item at the top of the stack ( in above example, node 9 is at top) and the last node is the node containing the bottom most item. Thus, a push() operation will add a new node in the front and a pop() remove a node from the front of the list. The SIZE of the stack is not important here because this representation allows dynamic stacks instead of static stacks, as with arrays.

 Source: classical data structure by samantha