Programming Data Structure Stack Implementation using Linked List with C++ | Data...

Stack Implementation using Linked List with C++ | Data Structure

-

Previously we have discussed about the introduction of stack and linked list, see here. In this article we will talk about stack implementation using linked list. Before deep-dive let’s go through a brief Introduction.

Stack:


Stack is a Data Structure often refers to as container of Objects. In a stack any insertion or deletion of object follows a method called LIFO, last-in-first-out. Which means, to access an object in stack, it is possible to access the recently inserted object. Object Insertion refers to as push() and Deletion Refers to as pop(). There is also a method naame – TOP(), which returns the reference of top element on the stack. Additionally, size(), returns the number of elements in the stack.  empty(), returns true, if the stack is empty.

An Example of StackInternet Web browsers store the addresses of recently visited sites on a stack. Each time a user visits a new site, that site’s address is “pushed” onto the stack of addresses. The browser then allows the user to “pop” back to previously visited sites using the “back” button.

Linked list:


Linked-list is linear Data-Structure, Which made up of nodes sometimes also refers to as Objects. Each node stores a link or pointer (address) namely next, to the next node of the list (singly linked-list). Node or Object of a doubly linked-list stores link of both prev and next nodes.There are mainly two types of linked list: Doubly, and singly linked-list. But, In practical cases doubly linked-list are used most. Head points to the node at the start of the list. Head of a linked-list basically the top of the stack. Tail points to the node at the end of the list. We really don’t need to track or, care about the tail of a linked-list. Because, we only can access the top element of a stack. An element x in the list, x.next points to its successor element, x.prev points to its predecessor.

Three types of operation we mainly perform on a linked-list. Insertion, Deletion, and Search. INSERT(L, x) inserts an element x into linked list L. DELETE(L, x) delete an element x from the linked-list L. SEARCH(L, x) perform a linear search to find an element x in the linked list L. However, Searching in linked list like hunting for treasure. Going to the 1st-person, who has the address of 2nd-person, and then go to the 2nd person looking for 3rd-person, and so on.

Stack implementation - CS School

Before going through stack implementation using linked list, definitely check out the stack implementation using array

Limitation of Array | Stack implementation using linked-list


To implement stack using array, we need a predefined array of fixed size. Therefore we can not increase the size of array as per requirement. Another problem with array that, if we create an array with a large size, it wastes the extra spaces. Besides, if it is necessary to input new element in the array, we have to create a new array, and copying and pasting elements to new array, and completely deleting the old array. Which is really a problem. So, to avoid this 3 dimensional problem, we need linked-list. Stack implementation using linked-list will dynamically increase the stack when necessary. Now we will see a simple stack implementation using singly linked-list with C++. The list is called singly, because each node of the list stores a single link of next node. A node in a singly-list contains two main fields: the data field, and the link field, which is a pointer points to the address of next node. Besides, a node may also contain other satellite data.

Lets define a class Node, which holds two members: Data, which stores the node data, and another member next, that is a pointer, which holds the address of next node. besides, we make a linkedList class a friend that gives access the class Node’s private members.

[cpp]class Node{
private:
string Data;
string *next;
friend class LinkedList;
};[/cpp]

Next, we define the class LinkedList for the actual linked list. It supports a number of member functions, including a constructor and destructor and functions for insertion and deletion. Its private data consists of a pointer to the head node of the list.

[cpp]
class LinkedList {
public:
LinkedList();//empty list constructor.
~LinkedList();//destructor.
bool empty() const; //is the list empty?
const string& front() const; // get front element.
void addFront(const string& e); // add to front of list.
void removeFront();
private:
Node *head; //points to the head of the node.};
[/cpp]

The LinkedList constructor creates an empty list by setting the head pointer to NULL. The destructor repeatedly removes elements from the list. To test whether the list is empty, we simply test whether the head pointer is NULL.

[cpp]
LinkedList::LinkedList():head(NULL){}
LinkedList::~LinkedList() //destructor
{while(!empty())
removeFront()}
bool LinkedList::empty() const // is the list empty?
{ return head == NULL; }
const string& LinkedList::front() const // get front element
{ return head−>Data; }
[/cpp]

Insertion


We can easily insert an element at the head of a singly linked list. We first create a new node, and set its Data value to the desired string and set its next link to point to the current head of the list. We then set head to point to the new node.

Stack Implementation

Figure: Insertion of an element of an element at the head of a singly linked-list. (a). before the insertion. (b). creation of a new node. (c). after the insertion.

Note that access to the private members Data and next of the Node class would normally be prohibited, but it is allowed here because LinkedList was declared to be a friend of Node.

[cpp]
void LinkedList::addFront(const string& e) { // add to front of list
Node *nNode = new Node; // create new node
nNode−>Data = e; // store data
nNode−>next = head; // head now follows nNode.
head = nNode; // nNode is now the head}
[/cpp]

Deletion


Deletion or remove is essentially undo the operations performed for insertion. We first save a pointer to the old head node and advance the head pointer to the next node in the list. We then delete the old head node.

stack implementation

Figure: Removal of an element at the head of a singly linked list: (a) before the removal. (b). delete the old new node. (c) after the removal.

[cpp]
void LinkedList::removeFront() { // remove front item
Node *old = head; // save current head
head = old−>next; // skip over old head
delete old; // delete the old head}
[/cpp]

We assume that the user has checked that the list is nonempty before applying this operation. (A more careful implementation would throw an exception if the list were empty.) The function deletes the node in order to avoid any memory leaks. We do not return the value of the deleted node. If its value is desired, we can call the front function prior to the removal.

//This is the end of general discussion on stack implementation using Linked-list. Next we will talk about other implementation of stack in practical cases.

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Latest Articles

Property Decorator | Getters Setters and Deleters in Python

In this article, we will talk about the Property Decorator in Python. It enables the class functionality...

Dictionaries | HashMap in Python | Working with Key-Values

Dictionaries in Python is similar to Hashmap comparing to other languages. It stores data as a key-value...

Hash Table | Indexing | Hashing Algorithm | Python Implementation

This article will talk about a high-level view of the Hash Table. As a programmer, this technique...

Eigenvector Eigenvalue | Linear Algebra Fundamentals

Eigenvector ($bar{v}$) in linear algebra is a non-zero vector (matrix) that doesn't change its direction during linear...

Pivot Table | Microsoft Excel | Create Data Insight Easily

Pivot table in microsoft Excel is an useful function that gives us a way to create insight...

Macro Function in Microsoft Excel | Automate Repetitive Task

This article we will talk about the Macro. It is a function in microsoft excel which basically...

Must read

Dictionaries | HashMap in Python | Working with Key-Values

Dictionaries in Python is similar to Hashmap...

You might also likeRELATED
Recommended to you