× Home

Implementing stack using linkedlist

Implementing stacks using linkedlists:

We can now consider a singly linked list. Follow the illustration below.

Consider this linked list functioning as a stack. And as you know, we have two sides of a linked list, one the head, and the other pointing to NULL. We consider top of stack at the head side.

Why the head side? Because that's the head node of the linked list, and insertion and deletion of a node at head happens to function in a constant time complexity, O(1). Whereas inserting or deleting a node at the last position takes a linear time complexity, O(n).
So that stack equivalent of the above illustrated linked list look something like this:

When is our stack empty or full?

Stacks when implemented with linked lists never get full. We can always add a node to it. There is no limit on the number of nodes a linked list can contain until we have some space in heap memory. Where as stacks become empty when there is no node in the linked list, hence when the top equals to NULL.
Condition of stack full : When heap memory is exhausted .
Condition for stack empty: top == NULL

We will refer head node as the top node.

These interpretations will heap us implement the operations, isEmpty and isFull.

Implementing all the stack operations using Linked lists

Before writing the codes, we must discuss the algorithm we'll put into operations. Let's go through them one by one.

1. isEmpty: It just checks if our top element is NULL.
2. isFull: A stack is full, only if no more nodes are being created using malloc. This is the condition where heap memory gets exhausted.
3. Push The first thing we need before pushing an element is to create a new node. Check if the stack is not already full. Now, we follow the same concept we learnt while inserting an element at the head or at the index 0 in a linked list. Just set the address of the current top in the next member of the new node, and update the top element with this new node.

4. Pop: First thing is to check if the stack is not already empty Now, we follow the same concept we learnt while deleting an element at the head or at the index 0 in a linked list. Just update the top pointer with the next node, skipping the current top.

code

isEmpty()

int isEmpty(struct Node* top){
if (top==NULL){
return 1;
}
else{
return 0;
}
}

isFull()

We don't have to make it seperate function as we can intend this in push function if the new node gets created that means there is space in heap

int isFull(struct Node* top){
struct Node* p = (struct Node*)malloc(sizeof(struct Node));
if(p==NULL){
return 1;
}
else{
return 0;
}
}

push()

  • Create a struct Node* function push which will return the pointer to the new top node.
  • We’ll pass the current top pointer and the data to push in the stack, in the function.
  • Check if the stack is already not full, if full, return the condition stack overflow.
  • Create a new struct Node* pointer n, and assign it a new memory location in the heap.
  • Assign top to the next member of the n structure using n-> next = top, and the given data to its data member.
  • Return this pointer n, since this is our new top node.

struct Node* push(struct Node* top, int x){
if(isFull(top)){
printf("Stack Overflow\n");
}
else{
struct Node* n = (struct Node*) malloc(sizeof(struct Node));
n->data = x;
n->next = top;
top = n;
return top;
}
}

pop()

  • Create an integer function pop which will return the element we remove from the top.
  • We’ll pass the reference of the current top pointer in the function. We are passing the reference this time, because we are not returning the updated top from the function.
  • Check if the stack is already not empty, if empty, return the condition stack underflow.
  • Create a new struct Node* pointer n, and make it point to the current top. Store the data of this node in an integer variable x.
  • Assign top to the next member of the list, by top = top->next, because this is going to be our new top.
  • Free the pointer n. And return x.

Here we are passing the address of top, this can be avoided if we will declare top as base address.

int pop(struct Node** top){
if(isEmpty(*top)){
printf("Stack Underflow\n");
}
else{
struct Node* n = *top;
*top = (*top)->next;
int x = n->data;
free(n);
return x;
}
}

peek()

This operation is meant to return the element at a given position. Do mind that the position of an element is not the same as the index of an element. In fact, there is nothing as an index in a linked list. Refer to the illustration below.

Peeking in a stack linked list is not as efficient as when we worked with arrays. Peeking in a linked list takes O(n) because it first traverses to the position where we want to peek in. So, we’ll just have to move to that node and return its data.

int peek(struct Node *top, int pos)
{
struct Node *ptr = top;
for (int i = 0; i < pos - 1 && ptr != NULL; i++)
{
ptr = ptr->next;
}
if (ptr != NULL)
{
return ptr->data;
}
else
{
return -1;
}
}

stackTop()
This operation just returns the topmost value in the stack. That is, it just returns the data member of the top pointer.

int stackTop(struct Node *top)
{
return top->data;
}

stackBottom()
This operation just returns the topbottom value in the stack. That is, it just returns the data member of the bottom element.

int stackBottom(struct Node *top)
{
struct Node *ptr = top;
while (ptr->next != NULL)
{
ptr = ptr->next;
}
return ptr->data;
}

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

void linkedListTraversal(struct Node *top)
{
printf("Top->");
while (top != NULL)
{
printf("%d->", top->data);
top = top->next;
}
printf("\n");
}
int isEmpty(struct Node *top)
{
if (top == NULL)
{
return -1;
}
else
{
return 0;
}
}

struct Node *push(struct Node *top, int data)
{
struct Node *p = (struct Node *)malloc(sizeof(struct Node));
if (p == NULL)
{
printf("Stack overflow");
}
else
{
p->data = data;
p->next = top;
top = p;
return top;
}
}
int pop(struct Node **top)
{
if (isEmpty(*top))
{
printf("Stack underflow");
}
else
{
struct Node *n = *top;
int x = n->data;
*top = (*top)->next;
free(n);
return x;
}
}

int peek(struct Node *top, int pos)
{
struct Node *ptr = top;
for (int i = 0; i < pos - 1 && ptr != NULL; i++)
{
ptr = ptr->next;
}
if (ptr != NULL)
{
return ptr->data;
}
else
{
return -1;
}
}
int stackTop(struct Node *top)
{
return top->data;
}

int stackBottom(struct Node *top)
{
struct Node *ptr = top;
while (ptr->next != NULL)
{
ptr = ptr->next;
}
return ptr->data;
}
int main()
{
struct Node *top = NULL;

top = push(top, 34);
top = push(top, 36);
top = push(top, 38);
// push(top, 36);
linkedListTraversal(top);
int element = pop(&top);
linkedListTraversal(top);
printf("The element at position %d is %d\n",0,peek(top,8));
printf("The element at top is %d",stackTop(top));
return 0;
}