Linked Stack

An array implementation of stack has certain limitations. One of the limitations of array implementation of stack is that stack cannot grow or shrink dynamically. This drawback can be overcome by using linked implementation.

A stack implemented using a linked list is also called linked stack.

Each element of the stack will be represented as a node of the list. The addition and deletion of a node will be only at one end. The first node is considered to be at the top of the stack, and it will be pointed to by a pointer called top. The last node is the bottom of the stack, and its link field is set to Null.

 

Singly linked list is suitable to implement stack using linked organization.

An empty linked stack will have Top=Null. Insertion and deletion of a node will be only at the end pointed by Top.

The creation, insertion (push) and deletion (pop) of data in a linked stack: 

 

Linked stack implementation:

class Stack_Node   // node of linked stack

{

public:

int data;

Stack_Node *link;

};

class Stack      // linked stack implementation

{

private:

Stack_Node *Top;

int Size;

int IsEmpty();

public:

Stack()

{

Top = Null;

Size = 0;

}

int GetTop();

int Pop();

void Push( int Element);

int CurrSize();

};

Operations on Linked Stack

The memory for each node is dynamically allocated on the heap. So when an item is pushed, a node for it is created, and when an item is popped, its node is freed.

Push operation: The Top is initialized to Null to indicate empty stack. The Push() function dynamically creates a new node. After creating a new node, the pointer variable Top should point to the newly added node in the stack.

void Stack :: Push(int value)

{

Stack_Node* NewNode;

NewNode = new Stack_Node;

NewNode->data = value;

NewNode->link = Null;

NewNode->link = Top;

Top = NewNode;

}

Pop operation: when an item is popped, a node at the top is deleted. But before performing pop operation a check has to be made whether the list is empty or not.

int Stack :: Pop()

{

Stack_Node* tmp = Top;

int data = Top->data;

if(!IsEmpty())

{

Top = Top->link;

delete tmp;

return(data);

}