Stack Operation using Linked List in C

Back to: Data Structures and Algorithms Tutorials

Stack Operation using Linked List in C:

In this article, we will discuss How to Implement Stack Operations using a Linked List in C Language with Examples. Please read our previous article discussing Stack Implementation using Linked List.

Stack Operation using Linked List in C

Let’s understand all the operations that we can perform on the stack using a linked list. The first operation is Push.

How to add an element to the stack using the push function:

This function will insert an element into the stack. It takes a value as a parameter that has to be pushed inside the stack. Here, assume that the Top pointer is global. It is a pointer of type Node, similar to the head or first pointer of a linked list.

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

This is the Node structure in C language. In the push function, we first check for the full condition (if (t == NULL)). To do that, we create a new Node. If the Node is not created, then it means the stack is full, so we print a message “Stack Overflow”. If t is not equal to null, we add the given value to this node (t->data = x). Then, we make t’s node point to the Top pointer (t->next = Top). Finally, Top will point to the newly inserted node, i.e., Top = t.

void push(int x) {
  struct Node * t;
  t = (struct Node * ) malloc(sizeof(struct Node));

  if (t == NULL)
    printf("stack is full\n");
  else {
    t -> data = x;
    t -> next = top;
    top = t;
  }
}

These are the steps for the push function. Here, we have inserted a new node before the head or first node of the linked list. So, the time taken is constant. This function also works when inserting the first node of the linked list. Let us explain.

To insert the first node using the push function:

Before inserting the first node, the Top pointer will be null. The push function will create a new node (t). Then, it will check for a null condition, but since t is not null, the control will shift to the other part. In the else part, the value will be assigned to t’s data, t’s next will be pointed to the Top pointer (as Top is null, so t’s next will also be null), and finally, Top will point to t’s node. In this way, we can insert the first element of the linked list with the push function. So, our function works for both conditions: insertion before the first node and inserting the first node. Now, let us look at the pop function.

How to delete an element from the stack using the pop function:

We know well that deletion is done from the left side so that the time will be constant. You can also delete from the right side, but it will take O(n) time.

Let’s say we want to delete the first node, i.e., 7. Before deletion, we need to check for the stack empty condition (if (Top == NULL)). If the linked list is empty, we cannot delete any node. Inside the pop function, we will take a variable, i.e., x with a value of -1, and a pointer of type node, i.e., t. Next, we will check for the stack empty condition. If the condition is true, we will print a message “Stack is Empty”. In the else part, if the condition fails, we proceed with deleting the first node with the following steps.

1. Assign t to the Top pointer (t = Top).
2. Move Top to next node (Top = Top->next)
3. Store the t’s data in x (x = t->data) and delete the t node (free (t)).

After the else statement, we return the deleted value, which is x. If there are no values in the stack or linked list, our function will return -1. Therefore, if the function returns -1, it means the stack is empty.

int pop() {
  struct Node * t;
  int x = -1;

  if (top == NULL)
    printf("Stack is Empty\n");
  else {
    t = top;
    top = top -> next;
    x = t -> data;
    free(t);
  }
  return x;
}

This is the procedure for deleting an element from the stack using the pop function. Now, let’s look at the peek operation.

How to get an element from a specific position in the stack using the peek function:

This function will take a position as a parameter and return the value at that given position. For example, if the position is 1, then it will return 7; if the position is 2, then it will return 5, and so on. However, if the position is 10, and there is no 10th position in the linked list, it is an invalid position. Therefore, we will return -1. Let us explain how the peek function works.

To return the element to a given position, we need to traverse the linked list (left to right) from the first node to the given position. So, we need a pointer of type node, i.e., t, and point it to the Top pointer (Node* t = Top). Now, for each given position, t should move position-1 times. For example, if the position is 3, t will move 2 times. After moving 2 times, t will point to the 3rd node. We can move t using a for-loop until it reaches the given position or becomes null.

So, the loop will start from 0 (i = 0), and it will continue until t != Null and i < position-1. At every iteration, we check whether t is pointing to null; if it is pointing to null, then we don’t need to check further. Inside the for-loop, we move t to t’s next (t = t->next). This loop will position t at the given position if the position is valid. If it is invalid, t will become null. After the loop, we check for t != NULL. If it is valid, then return the element at that position (return t->data). If t is null, then we return -1.

int peek(int pos) {
  int i;
  struct Node * t = Top;

  for (i = 0; t != NULL && i < pos - 1; i++) {
    t = t -> next;
  }

  if (t != NULL)
    return t -> data;
  else
    return -1;
}

This is the peek operation, which finds the element at the given position. Now, let me show you the remaining three functions: StackTop(), isEmpty(), and isFull().

How to get the topmost element of the Stack using the StackTop function:

This function returns the topmost element of the stack. Inside the function, we check if Top is valid or not null. If it is valid, we return Top’s data (Top->data); otherwise, we return -1.

int StackTop (){
    if(Top)
        return Top->data;
    return -1;
}

How to check whether the stack is empty or not:

The isEmpty() function checks whether the stack is empty. If Top is null, the stack is empty; otherwise, it is not empty.

int isEmpty (){
    return Top? 0: 1;
}

So, if the top is not null, the function returns 0; otherwise 1.

How to check whether the stack is full or not:

The isFull() function is used to check whether the stack is full or not. Inside the function, we will create a new node and check if the created node is null or not. If it is not null, assign 1 to r (temporary variable); otherwise, assign 0 to r. After that, delete the node and return the value of r. If the return value is 1, it means the stack is full; otherwise, the stack is not full.

int isFull (){
    struct Node * t = malloc(sizeof(struct Node))
    int r = t ? 1 : 0;
    free (t);
    return r;
}

So, there are the basic operations that we can perform on the stack by using the linked list. All the operations that we discussed in this article take constant time.

Program to perform various operations on Stack using Linked List in C Language:

#include <stdio.h>

#include <stdlib.h>

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

void push(int x) {
  struct Node * t;
  t = (struct Node * ) malloc(sizeof(struct Node));

  if (t == NULL)
    printf("stack is full\n");
  else {
    t -> data = x;
    t -> next = Top;
    Top = t;
  }

}
int pop() {
  struct Node * t;
  int x = -1;

  if (Top == NULL)
    printf("Stack is Empty\n");
  else {
    t = Top;
    Top = Top -> next;
    x = t -> data;
    free(t);
  }
  return x;
}
void Display() {
  struct Node * p;
  p = Top;
  while (p != NULL) {
    printf("%d ", p -> data);
    p = p -> next;
  }
  printf("\n");
}

int peek(int pos) {
  int x = -1, i;
  struct Node * t = Top;

  for (i = 0; t != NULL && i < pos - 1; i++) {
    t = t -> next;
  }

  if (t != NULL)
    return t -> data;
  else
    return -1;
}

int StackTop() {
  if (Top)
    return Top -> data;
  return -1;
}

int isEmpty() {
  return Top ? 0 : 1;
}

int isFull() {
  struct Node * t = malloc(sizeof(struct Node));
  int r = t ? 1 : 0;
  free(t);
  return r;
}

int main() {

  push(9);
  push(4);
  push(5);
  push(7);

  printf("Stack is: ");
  Display();
  printf("Element at 2nd Position: %d \n", peek(2));
  printf("Element at Top of Stack: %d \n", StackTop());
  printf("Popped Element: %d \n", pop());
  printf("is stack Empty: %d \n", isEmpty());
  printf("is stack Full: %d \n", isFull());

  return 0;
}

Output:

Program to perform various operations on Stack using linked list in C++ language:

#include <iostream>
using namespace std;

class Node {
  public: int data;
  Node * next;
};

class Stack {
  private: Node * Top;
  public: Stack() {
    Top = NULL;
  }
  void push(int x);
  int pop();
  void Display();
  int peek(int pos);
  int StackTop();
  int isEmpty();
  int isFull();
};

void Stack::push(int x) {
  Node * t = new Node;
  if (t == NULL)
    cout << "Stak is Full \n";
  else {
    t -> data = x;
    t -> next = Top;
    Top = t;
  }
}

int Stack::pop() {
  int x = -1;
  if (Top == NULL)
    cout << "Stack is Empty \n";
  else {
    x = Top -> data;
    Node * t = Top;
    Top = Top -> next;
    delete t;
  }
  return x;

}

void Stack::Display() {
  Node * p = Top;
  while (p != NULL) {
    cout << p -> data << " ";
    p = p -> next;
  }
  cout << endl;
}

int Stack::peek(int pos) {
  int x = -1, i;
  Node * t = Top;

  for (i = 0; t != NULL && i < pos - 1; i++) {
    t = t -> next;
  }

  if (t != NULL)
    return t -> data;
  else
    return -1;
}

int Stack::StackTop() {
  if (Top)
    return Top -> data;
  return -1;
}

int Stack::isEmpty() {
  return Top ? 0 : 1;
}

int Stack::isFull() {
  Node * t = new Node;
  int r = t ? 1 : 0;
  delete t;
  return r;
}

int main() {
  Stack stk;

  stk.push(9);
  stk.push(4);
  stk.push(5);
  stk.push(7);

  cout << "Stack is: ";
  stk.Display();
  cout << "Element at 2nd Position: " << stk.peek(2) << endl;
  cout << "Element at Top of Stack: " << stk.StackTop() << endl;
  cout << "Popped Element: " << stk.pop() << endl;
  cout << "is stack Empty: " << stk.isEmpty() << endl;
  cout << "is stack Full: " << stk.isFull() << endl;
  return 0;
}

Output:

In the next article, I will discuss Parenthesis Matching Operation using Stack. In this article, I explain how to perform operations on a stack using a Linked List in C Language with examples. I hope you enjoy this Stack Operations article using the Linked List.