Stack Implementation using Linked List | C++ Code

You can implement the Stack data structure using a singly Linked List but you have to keep in mind that you have to perform all the Stack operations by following the LIFO (Last In First Out) principle. You also have to remember that all the Stack operations like push(), pop(), pee(), and isempty() must be performed under the constant time complexity of O(1).  

Stack operations using Linked List:

To implement a stack using a linked list, you have to create one top pointer that will always point to the head of the linked list or you can say the topmost node of the stack. Because here, in this case, you are not just going to store the variable inside the stack instead you are going to store the node of the list. All your important operations like push and pop are going to perform from the beginning of the list or you can say at the head (top) of the list. 

Push Operation into Stack

push(): To perform the insert operation into the stack, you have to insert an element at the beginning of the list. When your head (top) is pointing to NULL it means your stack is empty so to insert an element into the stack you have to create one new node with that element and assign the address of this node to the head (top). And whenever you want to add one new element, you can perform insert at the beginning operation on the list. 

Pop operation on Stack.

pop(): To remove the top element of the stack, you can simply delete the first node of the list because it is the topmost element present in the stack and as you know that the head (top) always points to the beginning of the list. After deleting the first node, the head (top) will start pointing to the second node which is now the top element of the stack.

peek(): To get the information about the top element of the stack, you can simply return what value is present in the first node of the list which is pointed by the head (top) pointer. If the head (top) is pointing to NULL it means no element is present in the stack.

isempty(): It is very simple to know if the stack is empty or not, if your head contains a NULL value it means your stack is empty.

There is no condition when the stack gets full when you are implementing Stack using Linked List because the size of the Linked List can increase or decrease at runtime.

Example: C++ code for the Implementation of Stack using Singly Linked List.

#include <bits/stdc++.h>
using namespace std;
class ListNode
{
public:
    int data;
    ListNode *next;
    // constructor
    ListNode(int data)
    {
        this->data = data;
        this->next = NULL;
    }
    // destructor
    ~ListNode()
    {
        int value = this->data;
        if (this->next != NULL)
        {
            delete next;
            this->next = NULL;
        }
        cout << "Pop a Node with value " << value << endl;
    }
};
// function to push element into stack
void push(ListNode *&top, int num)
{
    ListNode *temp = new ListNode(num);
    temp->next = top;
    top = temp;
}
// function to pop element from the stack
void pop(ListNode *&top)
{
    if (top == NULL)
    {
        cout << "Stack is Empty" << endl;
    }
    else
    {
        ListNode *temp = top;
        top = top->next;
        temp->next = NULL;
        delete temp;
    }
}
// function to check topmost element of stack
int peek(ListNode *&top)
{
    if (top == NULL)
    {
        cout << "Stack is Empty" << endl;
        return -1;
    }
    else
    {
        return top->data;
    }
}
// function to print all the element of stack
void printStack(ListNode *&top)
{
    ListNode *temp = top;
    while (temp != NULL)
    {
        cout << temp->data << endl;
        temp = temp->next;
    }
}
// function to check stack is empty or not
bool isEmpty(ListNode *&top)
{
    if (top == NULL)
    {
        return true;
    }
    return false;
}
int main()
{
    ListNode *top = NULL;
    // push elements into stack
    push(top, 20);
    push(top, 30);
    push(top, 40);
    push(top, 50);
    cout << "Element present at the top of stack :";
    cout << peek(top) << endl;
    pop(top);
    cout << "New top after deleting topmost element :";
    cout << peek(top) << endl;
    cout << "Elements present in the stack :" << endl;
    printStack(top);
    if (isEmpty(top))
    {
        cout << "Stack is Empty" << endl;
    }
    else
    {
        cout << "Stack is not Empty" << endl;
    }
}

Output:

Element present at the top of stack :50   
Pop a Node with value 50
New top after deleting topmost element :40
Elements present in the stack :
40
30
20
Stack is not Empty

You can observe that all the stack operations like push(), pop() and peek() are done within constant time complexity O(1) using a singly Linked List.

Stack Implementation using Array | C++ Code

The Stack data structure can be easily implemented using a 1D array. You can easily perform all the basic stack operations like push(), pop(), peek(), and isEmpty() in constant time O(1) without using any loop and by following the LIFO (Last In First Out) principle. 

To implement all the stack operations, you need one fixed-size array and a very important variable name top that always points to the topmost element of the stack data structure. In your case, the top variable is going to hold the index of the top element of the stack. 

• Initially, the top is initialized with a -1 value which means that your stack is empty and if you met a condition when (size of the array - top) is less than 1 then you can say your stack is full.

Stack operations using Array.

push(): It is a function used to insert an element at the top of the stack. 

• Check if the stack is full or not. When (SIZE - 1 == top), "STACK is FULL" you cannot insert any further value to terminate the function.
• If (SIZE-1 is not equal to top), increment the top value by 1 (top++) and initialize arr[top] = value.

pop(): It is a function used to delete an element from the top of the stack.

• Check if the stack is empty or not. When top == -1, "STACK IS EMPTY" there is no element present to delete so terminate the function.
• If top > -1, delete the top element by decreasing the top value by one. (top--).

peek(): It is a function that returns the topmost value present in the stack.

• Check if top == -1, the stack is empty so there is no element present in the stack.
• If top > - 1, return the top value using arr[top]. 

isEmpty(): It is a function to check if the stack is empty or not. If the stack is empty return TRUE else return FALSE.

• If top == -1, return true else return false.

Stack Implementation using Array

Example: C++ code for Implementation of Stack using Array.

#include <bits/stdc++.h>
using namespace std;

class Stack
{
public:
    // integer type pointer
    int *arr;
    int top;
    int size;
    // behaviour
    Stack(int size)
    {
        this->size = size;
        // dynamically allocating memory
        arr = new int[size];

        top = -1;
    }
    // function to push element in stack
    void push(int element)
    {
        if (size - 1 == top)
        {
            cout << "Stack OverFlow" << endl;
        }
        else
        {
            top++;
            arr[top] = element;
        }
    }
    // function to pop element in stack
    void pop()
    {
        if (top == -1)
        {
            cout << "Stack is Empty" << endl;
        }
        else
        {
            top--;
        }
    }
    // function to peek element in stack
    int peek()
    {
        if (top == -1)
        {
            cout << "stack is empty !!" << endl;
            return -1;
        }
        else
        {
            return arr[top];
        }
    }
    // check if stack is empty or not.
    bool isEmpty()
    {
        if (top == -1)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
};

int main()
{
    Stack s(5);

    s.push(20);
    s.push(30);
    s.push(40);
    s.push(50);

    cout << "Top Element: " << s.peek() << endl;
    // delete the top element of the stack which is now 50
    s.pop();
    // top element after deleting 50
    cout << "Top Element: " << s.peek() << endl;

    if (s.isEmpty())
    {
        cout << "Stack is Empty !!!" << endl;
    }
    else
    {
        cout << "Stack is not Empty !!!" << endl;
    }
}

Output:

Top Element: 50
Top Element: 40
Stack is not Empty !!!

Implementation of Stack using Array is easy to use but it is not dynamic in nature so we can increase or decrease the size of Stack at runtime. To solve this problem, you can use Linked List for the implementation of Stack because as we know that the size of the Linked List data structure is not fixed.

Stack Data Structure Introduction.

Stack is a Linear Data Structure that follows a LIFO (Last In First Out) principle. 

To understand stack data structure let's take a real-life example of the arrangement of plates as shown below. You can observe that plate 1 is placed at the bottom and plate 2 is placed on top of plate 1 similarly plate 3 is placed on top of plate 2. 

Now if you want to put one more late, the easiest way to arrange them is to put the next plate on top of all the other plates, and similarly, if you want to pick one plate then the easiest way is to pick the topmost plate from the stack of plates. 

You can observe that the plate which you are putting, at last, is present on the top and you have to pick that plate first to take the other plates. So this is the basic idea of the LIFO principle of stack data structure. 

Real-Life use of Stack Data Structure.

• Records of your phone logs use the Stack data structure to store all your call records so you get the most recent call details at the top.
• The browser saves your browsing history using the Stack data structure so you can see most of the details of the most recently visited page at the top.
• For recursive function calls, you have to be sure that your function calls do not each stack overflow exception. 

You can implement the Stack data structure in two different ways, 

• Stack Implementation using 1D Array.
• Stack Implementation using Singly Linked List.

There are basically three important operations that you can perform on the Stack and with the help of these operations on the stack, you can solve many complex coding problems. These operations are:

push(): It is used to push any element inside the given stack. It is the rule of stack data structure that you cannot directly push an element in between or at the bottom of the stack. You can push it on the top of the stack.

Push Operation 

pop(): It is used to remove an element from the top of the stack. You cannot directly remove the middle or last element from the stack.

Pop Operation

peek(): It is used to check which element is present at the top of the stack. It returns the value which is present a the top but it does not perform any changes.

All the above operations, push(), pop() and peek() take constant time O(1)  

(getButton) #text=(Stack Implementation using Array) #icon=(link) #color=(#2339bd)

(getButton) #text=(Stack Implementation using Linked List) #icon=(link) #color=(#2339bd)

Program Reverse a String using Stack in C++

Problem: Given a String, reverse the given string using stack. 

Input: str = "algolesson"
Output: str = "nosselogla"

Input: str = "orange"
Output: str = "egnaro"

Steps to reverse the string using stack.

• Create one empty Stack.
• Push all the characters of the given string one by one into the stack.
• Create a new empty string.
• Add the top character of the stack to the empty string then pop the top character.  
• Repeat the fourth step until the stack gets empty and you will get the reverse of the given string.

Example: C++ Code to reverse a string using stack.

//C++ Program to reverse String using Stack

#include <iostream>
#include <stack>
using namespace std;

int main()
{
    string str = "orange";
    stack<char> sc;
    string s = "";
    //push all the char to the stack
    for (int i = 0; i < str.size(); i++)
    {
        sc.push(str[i]);
    }
    //pop all the char from the stack

    // and add then to new empty string.
    while (!sc.empty())
    {
        s += sc.top();
        sc.pop();
    }
    cout << "Reverser String " << s << endl;
}

Output:

Reverser String egnaro

• Time Complexity: O(n)
• Space Complexity: O(n)

As you can see that we are using extra space to reverse the given string which means that this is not an efficient algorithm because we solve the same problem without using any extra space and without using a stack. 

Example: C++ Code to reverse a string without using extra space and without using stack.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string str = "orange";

    //size of the given string
    int n = str.size();
    
    for (int i = 0; i < n / 2; i++)
    {
        swap(str[i], str[n - 1 - i]);
    }
    cout << "Reverse String " << str << endl;
}

Output:

Reverse String egnaro

Time Complexity: O(n).

Space Complexity: O(1)

Binary Search Algorithm with code in C++.

Binary Search is one the most popular and widely used search algorithms used to search whether a particular element is present in the given sorted array or not. It is much better than the Linear search algorithm because it is much faster.  

Problem: Given a sorted array of integers arr[ ] of size n and a target element x, write a C++ program to search the position of x in the given array.

Input: arr[ ] = {7, 10, 11, 15, 20, 30, 26}   x = 20

Output: 4
x is present at index 4.

Input: arr[ ] = {11, 15, 22, 30, 35, 43, 60, 75, 120}   x = 65

Output: -1
x is not present in the arr[ ].

Binary Search Explanation. 

When you try to find the target element in the given array, the worst-case scenario is that when you have to check each element of the given array and it leads to O(n) time complexity. But when the array elements are arranged in sorted order, you can use this extra information to reduce the time complexity to O(log n). 

• If you use a binary search on 100 elements to find your target, the worst-case scenario would be 10 searches. Can you imagine a huge performance improvement? 😲

You get this huge performance improvement because, for each iteration, you reduce the number of elements you will be looking at in half. The idea is to compare the target element to the middle element of the array. 

• If you find the target element is equal to the middle element, return the position of the middle element and stop.
• If the target element is smaller than the middle element, continue searching on the left side of the middle element. high = mid-1
• If the target element is greater than the middle element, continue searching on the right side of the middle element. low = mid+1
• Repeat all three steps until you find the matching element else return -1.

Example: C++ code for Binary Search Algorithm.

#include <iostream>
using namespace std;

int binarySearch(int arr[], int n, int key)
{ 

    int low = 0, high = n - 1; 

    while (low <= high)
    {
        int mid = low + (high - low) / 2;
        //target is found
        if (arr[mid] == key)
        {
            return mid;
        }
        else if (arr[mid] < key) //target might be present in right half
        {
            low = mid + 1;
        }
        else    //target might be present in left half
        {
            high = mid - 1;
        }
    }
    return -1;
}

int main()
{

    int arr[] = {7, 10, 11, 15, 20, 30, 36};
    // size of given array
    int size = sizeof(arr) / sizeof(arr[0]);
    // target element to be find
    int x = 20;

    int index = binarySearch(arr, size, x);
    if (index == -1)
    {
        cout << "Value is not present in the given array." << endl;
    }
    else
    {
        cout << "Value present at index: " << index << endl;
    }
}

Output:

Value present at index: 4

• Time Complexity: O(log n)
• Space Complexity: O(1)

Important points to note: 

int low = 0, high = n - 1;

low and high work like a boundary and we will be looking at elements inside the boundary to find out the target element x and these boundaries get change with each iteration until we found our target loop gets terminated when low == high.

int mid = (high + low) / 2; //formula 1 
int mid = low + (high - low) / 2; //formula 2

Now, a few of you might be thinking that why we are using formula 2 instead of formula 1 as both the formula is going to give the same result? The answer to this question is to avoid integer overflow as the maximum value the integer datatype can hold is 2147483647.  So when you in case of adding two bigger numbers and try to store them in integer datatype it will give you a wrong answer. 

I believe the remaining part of the code was easy to understand with the help of the above explanation and animation gif. If you have any questions or suggestions related to the post, you can share them with us in the comment section below.

Linear Search Algorithm with code in C++.

Linear Search is a searching algorithm that is also known as a sequential search. It is one of the very popular searching algorithms that is used to search whether an element is present in the given array or not. 

Problem: Given an array of integers arr[ ] of size n and a target element x, write a C++ program to search the position of x in the given array. You can return -1 in the element x is not present in the given array. 

Input arr[ ] = {20, 10, 7, 30, 11, 15, 36} 
x = 11

Output:  4
Element is present at index 4

Input arr[ ] = {5, 10, 8, 30, 12, 70, 25, 19}
x = 15

Output: -1 
Element is not present at any index.

Steps to follow:

• Start from the 0 index element of the given array and start comparing each element with x.
• If you find an index element matches with x, return the index. arr[index]  == x
• If you are unable to find the matching element in the array, return -1.

Example: C++ Program for Linear search.

#include <iostream>
using namespace std;

// Function for Linear Search
int linearSearch(int arr[], int n, int x)
{
    int i;
    for (i = 0; i < n; i++)
    {
        if (arr[i] == x)
        {
            return i;
        }
    }
    return -1;
}
int main()
{
    // Elements present in the array
    int arr[] = {20, 10, 7, 30, 11, 15, 36};
    // size of given array
    int size = sizeof(arr) / sizeof(arr[0]);
    // Element x to be search in the array
    int x = 11;
    int pos = linearSearch(arr, size, x);
    if (pos == -1)
    {
        cout << "Element " << x << " is not present in the given array." << endl;
    }
    else
    {
        cout << "Element " << x << " is present at index " << pos << endl;
    }
}

Output:

Element 11 is present at index 4

• Time Complexity: O(n).
• Space Complexity: O(1).

Mostly in real-life applications, we rarely use a Linear search algorithm. We mostly use a Binary search algorithm with time complexity O(log n) which is more efficient than this linear search.

How To Enable Auto Format On Save in VS Code?

Whenever we write some code in our Visual Studio Code, we have to spend our precious time formatting the code for better readability and understanding. Any code with poor formatting is hard to understand and debug. Proper positioning of curly brackets and indentation is very important because it helps us to understand which part of the code is ending where.

It is okay to format a few lines of code manually but imagine if we are writing 1000 lines of code and we are spending a lot of our time in formating them correctly. But many Visual Studio Code users don't know about the auto-formatting feature that is available in VS Code. 

Today we are going to save a lot of your precious time by letting you know how you can enable this feature on VS Code. 

Step 1: Open your Visual Studio Code and click on the Settings icon from the lower-left corner and then select Settings.

Step 2: Now, inside the User section, select Text Editors and expand this section. You can see a setting option name "Formatting" select that option.

Step 3: Inside Formatting, select the check box with the name "Format On Save" and that's it. 

Now you will observe that whenever you write and piece of code and click on Save, your code will automatically get formatted. Now you just enjoy writing beautiful code without worrying about formatting them. 

ASP.NET Core Tutorial

In this course of ASP.NET Core, we will cover all the basic, intermediate, and advanced ASP.NET core concepts that help you build data-driven web applications by the end of this course you will be able to perform all the CRUD operations that are Create, Read, Update and Delete using Sequal server as our database. 

The topics which we are going to cover in detail are-

• ASP.NET Core.
• ASP.NET Core MVC.
• ASP.NET Core Identity.
• Entity Framework Core.

What is ASP.NET Core?

ASP.NET Core is a cross-platform, high-performance, open-source framework for building modern, cloud-based, Internet-connected applications. ASP.NET Core is a redesign of ASP.NET 4.x and earlier it was named ASP.NET 5 and later is renamed ASP.NET Core.

Few benefits and features of ASP.NET Core.

Cross-Platform: ASP.NET Core applications can be developed and run across different platforms like Windows, macOS, Linux. ASP.NET Core applications can be hosted on IIS, Apache, Docker, and even Self-host in your own process.

Because of One Unified Programming Model for MVC and Web API, both the MVC Controller class and the ASP.NET Web API Controller class inherit from the same Controller base class and returns IActionResult.

ASP.NET Core has great build-in support for Dependency Injection which is a very great feature to learn.

ASP.NET Core Testability feature makes unit testing easy for developers.

It is an Open Source technology so it is continuously growing and improving with the support of developers from the open-source community.

Modular: ASP.NET Core provides modularity with Middleware Components. Both the request and response pipelines are composed using the middleware components. A rich set of built-in middleware components are provided out of the box. Custom Middleware Components can also be created.

Middleware - Is a piece of software that can handle HTTP request or response

Prerequisites for this course:

• Basic understanding of HTML, CSS, and C#.
• Prior MVC knowledge is helpful but not required. 

ASP.NET Core Project File.

.csproj or .vbproj depending on the programming language used.

No need to unload the project to edit the project file.

File or Folder references are no longer included in the project file.

The File System determines what files and folders belong to the project.

TargetFramework.

Specifies the target framework for the application.

To specify a target framework we used Target Framework Moniker (TFM)

AspNetCoreHostingModel.

Specifies how the application should be hosted.

InProcess or OutofProcess.

InProcess hosts the app inside of the IIS working process (w3wp.exe)

OutProcess hosting model forward web requests to a backend ASP.NET Core app running the Kestrel server. The default is OutofProcess hosting.

PackageReference.

Used to Include a reference to the NuGet package that is installed for the application.

Merapackage - Microsoft.AspNetCore.App

A metapackage has no content of its own. It just contains a list of dependencies (other packages).

When the version is not specified, an implicit version is specified by the SDK. Rely on the implicit version rather than explicitly setting the version number on the package reference. 

Main method in ASP.NET Core.

A Console application usually has a Main() method.

Why do we have a Main() method in ASP.NET Core Web Application?

ASP.NET Core application initially starts as a Console application.

This Main() method configures ASP.NET Core and starts it and at that point it becomes an ASP.NET Core web application.

The Main() method called "CreateWebHostBuilder" and we are passing the command line argument to it. We can notice that "CreateWebHostBuilder" return "IWebHostBuilder" and "Build()" is called on that which build the webhost on which ASP.NET Core Application and on this we add "Run()" and start listening the incoming Http request.

We are also configuring the "Startup" class using the extension method named ".UseStartup"

Going to the definition of "Startup" class we find two important method "ConfigureService" configure the service required for our application and "Configure" configure our application request processing pipeline 

Some of the Tasks that CreateDefaultBuilder() performs.

Setting up the web server. Loading the host and application configuration from various configuration sources and Configuring logging.

An ASP.NET Core application can be hosted.

• InProcess or 
• OutofProcess.

ASP.NET Core InProcess Hosting.

To configure InProcess hosting.

<AspNetCoreHostingModel>InProcess</AspNetCoreHostingModel>

CreateDefaultBuilder() method calls UseIIS() method and host the app inside of the IIS worker process (w3wp.exe or iisexpress.exe)

InProcess hosting delivers significantly higher request throughput than OutOfProcess hosting 

To get the process name executing the app.

System.Diagnostics.Process.GetCurrentProcess().ProcessName

With out-of-process hosting.

2 Web Servers - Internal and External Web Server.

The internal web server is Kestrel.

The external web server can be IIS, Nginx, or Apache.

What is Kestrel?

Cross-Platform Web Server for ASP.NET Core.

Kestrel can be used, by itself as an edge server.

The process used to host the app is dotnet.exe.

Dependency Injection in ASP.NET Core.

What is Dependency Injection?

Dependency Injection (DI) is the technique to achieve IOC (Inversion of Control). Inversion of Control means we need to make our code loosely coupled so in the future if there are any changes then there should not be any tight coupling between any two classes of object.

This is the basic structure of our project when we are not using Dependency Injection and we are using some service(class) inside one or more Controller then we create an object of the service using the "new" keyword and suppose in the future if we make any changes like changing the name of the service then we have to make those changes inside all Controllers. This is an example of tightly coupling.

Now let's understand what happens when we work with Dependency Injection, suppose I have only one service so to work with dependency injection I need to create one interface of my service. Now I will not work directly with the service I will use an interface to create this field and to store the object of this particular service. Now if we are making any changes in service then we don't have to make any changes in the control which is using it.

Now one important question that may come to our mind that where I will create the instance of the service and how the application will come to know that this interface is resolved by using this particular class. ???

In the concept of dependency injection, we generally create a container, and inside that container, we define some settings. 

How to configure Dependency Injection in ASP.NET Core?

ASP.NET Core provides the built-in support for DI. Dependencies are registered in containers and the container in ASP.NET core is IServiceProvider. Services are typically registered in the application's Startup.ConfigureService method.

Service Lifetime.

Service can be registered with following lifetimes-

• Transient (AddTransient<>) - A  new instance of the service will be created every time it is requested.
• Scoped (AddScoped<>) - These are created once per client request. For each HTTP request
• Singleton (AddSingleton<>) - Same instance for the application.