Stack Using Linked List


Stack Using Linked List

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means that the last element added to the stack is the first one to be removed. It has two main operations: push (to add an element) and pop (to remove the top element).
Stack Implementation using Linked List:

A linked list is a data structure where each element (node) contains a data field and a reference (link) to the next node in the sequence. In a linked list implementation of a stack, the top of the stack corresponds to the first node in the linked list.


Algorithm

1.Define the Node Structure:
Create a structure to represent a node in the linked list. This structure should have two members: one for storing the data and another for pointing to the next node.c

struct Node {
    int data;
    struct Node* next;
};

2.Initialize an Empty Stack:
Create a pointer to the top of the stack (top) and initialize it to NULL.
struct Node* top = NULL;

struct Node* top = NULL;

3.Push Operation:
Allocate memory for a new node.
Set the data of the new node.
Update the 'next' pointer of the new node to point to the current top.
Update the 'top' pointer to the new node.

void push(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = top;
    top = newNode;
}

4.Pop Operation:
Check if the stack is not empty (i.e., top is not NULL).
If not empty, store the data of the top node, update 'top' to point to the next node, and free the memory of the removed node.

int pop() {
    if (top == NULL) {
        printf("Stack is empty.\n");
        return -1;  // or any value to indicate an error
    }

    int poppedValue = top->data;
    struct Node* temp = top;
    top = top->next;
    free(temp);

    return poppedValue;
}


5.Display Stack :

Check if the Stack is Empty:
If the stack is empty (i.e., top is NULL), print a message indicating that the stack is empty.

Traverse and Print:
If the stack is not empty, initialize a temporary pointer to the top of the stack.
Traverse the stack using a loop until the temporary pointer becomes NULL.
Print the data of each node as you traverse.

void displayStack() {
    if (top == NULL) {
        printf("Stack is empty.\n");
    } else {
        struct Node* temp = top;
        printf("Stack content:\n");
        while (temp != NULL) {
            printf("%d\n", temp->data);
            temp = temp->next;
        }
    }
}



Complexity Analysis

Let's analyze the time complexity of the basic stack operations (push, pop, and display) for the linked list implementation:

Push Operation:Time Complexity: O(1)
The push operation involves creating a new node, updating pointers, and performing some basic assignments. These operations take a constant amount of time, making the time complexity of push O(1).


Pop Operation:Time Complexity: O(1)
Similar to push, the pop operation involves updating pointers, freeing memory, and performing basic assignments. These operations also take a constant amount of time, resulting in a time complexity of O(1).


Display Operation:Time Complexity: O(n)
The display operation involves traversing the entire linked list, where "n" is the number of elements in the stack. As each element needs to be visited once, the time complexity is linear with respect to the number of elements in the stack.

In summary:
Push and pop operations have constant time complexity O(1).
Display operation has a linear time complexity O(n), where "n" is the number of elements in the stack.

The space complexity for the linked list implementation is also important to consider:

Space Complexity: O(n)
The space complexity is linear with respect to the number of elements in the stack since each element is represented by a node, and additional space is used for pointers.

It's important to note that these complexities are based on the assumption of a singly linked list. If you were using a doubly linked list or another variant, the complexities might be different.

Stack using Linked List -C Implementation
/*******************************************************************************/

#include<stdio.h>
#include<conio.h>
#include <stdlib.h>
struct Node
{
 int data;
 struct Node *next;
};
struct Node *top=NULL;

void push(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = top;
    top = newNode;
}

int pop() {
    if (top == NULL) {
        printf("Stack is empty.\n");
        return -1;  // or any value to indicate an error
    }

    int poppedValue = top->data;
    struct Node* temp = top;
    top = top->next;
    free(temp);

    return poppedValue;
}

void displayStack() {
    if (top == NULL) {
        printf("Stack is empty.\n");
    } else {
        struct Node* temp = top;
        printf("Stack content:\n");
        while (temp != NULL) {
            printf("%d\n", temp->data);
            temp = temp->next;
        }
    }
}
void main()
{
 int ch;
 
 do
 {
  printf("\nMenu\n----\n1. Push\n2. Pop\n3.display\n4. Exit");
  printf("\nEnter the choice:");
  scanf("%d",&ch);
  switch(ch)
  {
   case 1:
        printf("Enter the data to push:");
        int data;
        scanf("%d",&data);
        push(data);
        displayStack();
         break;
   case 2:
        int rv;
        rv=pop();
        if(rv!=-1) printf("Popped Value is:%d\n",rv);
        displayStack();
        break;
   case 3:
    displayStack();
    break;
   case 4:
    exit(0);
   default:
    printf("There is no such operation:");
  }
 }
 while(1);
}

Comments

Post a Comment

Popular posts from this blog

Data Structures CST 201 KTU Third Semester Syllabus Notes and Solved Questions- Dr Binu V P 984739060

Dr BinuV P -About Me About The Course Syllabus Data Structures Lab CSL 201 ( Do the Programs to Understand the Concept Well) Model Question Paper CST 201 Data Structures University Question Papers CST 201 Data Structures Module-1 Basic Concepts of Data Structures 1.1 System Life Cycle 1.2 Algorithms , Performance Analysis  1.3 Space Complexity, Time Complexity  1.4 Asymptotic Analysis and Notations  1.5 Complexity Calculation of Simple Algorithms Module-2 Arrays and Searching  2.1 Polynomial representation using Arrays  2.2 Sparse matrix  2.3 Stacks  2.4 Queues 2.5 Circular Queues  2.6 Priority Queues 2.7 Double Ended Queues 2.8 Infix to  Postfix Conversion  2.9  Evaluation of Postfix Expression 2.10 Linear Search  2.11 Binary Search Module-3 Linked List and Memory Management 3.1 Linked List -Self Referential Structures  3.2 Dynamic Memory Allocation  3.3 Singly Linked List-Operations on Linked List 3.4 Doubly Linked List 3.5 Circular Linked List  3.6 Stack using Linked List  3.7 Queue
Read more

Stack

Image
A stack is a fundamental data structure in computer science and programming that follows the Last-In, First-Out (LIFO) principle . It is named "stack" because it resembles a stack of items, like a stack of plates or books, where you can only add or remove items from the top. Stacks are used for various purposes in programming and are essential in many algorithms and applications. Let's delve into the details of stacks: Key Operations:  A stack typically supports two primary operations: Push: This operation adds an element to the top of the stack. It is analogous to placing an item on top of the stack. Pop: This operation removes and returns the top element of the stack. It is like taking the top item off the stack. Additionally, stacks often provide the following operations: Peek (or Top): This operation retrieves the top element without removing it. It allows you to examine the top item without modifying the stack. IsEmpty: This operation checks if the stack is empty.
Read more

Quick Sort

Quick sort is a popular sorting algorithm that uses a divide-and-conquer strategy to efficiently sort an array or list. It works by selecting a "pivot" element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted. Here's a detailed algorithm for the Quick Sort algorithm: Algorithm: Quick Sort 1.Choose a pivot element from the array. This can be done in various ways, such as selecting the first element, the last element, or a random element. The choice of the pivot can affect the algorithm's performance. 2,Partition the array into two sub-arrays:     Elements less than the pivot (left sub-array).     Elements greater than the pivot (right sub-array). 3.Recursively apply the Quick Sort algorithm to the left and right sub-arrays. 4.Combine the sorted left sub-array, pivot, and sorted right sub-array to obtain the final sorted ar
Read more