Scribd
Upload
293 views13 pages

1.2.b. Stack ADT

The document discusses stacks and their implementation using linked lists. It defines a stack as a linear data structure that follows the LIFO principle. Examples of real-world stacks like piles of books and cups are given. The key operations of a stack like push, pop and peek are described. It then explains how to implement a stack using a linked list by maintaining the top pointer and performing insertion and deletion at one end. Code snippets for push, pop and other operations on the linked list implementation of a stack are provided.

Uploaded by

Mohamed Bilal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
293 views13 pages

1.2.b. Stack ADT

The document discusses stacks and their implementation using linked lists. It defines a stack as a linear data structure that follows the LIFO principle. Examples of real-world stacks like piles of books and cups are given. The key operations of a stack like push, pop and peek are described. It then explains how to implement a stack using a linked list by maintaining the top pointer and performing insertion and deletion at one end. Code snippets for push, pop and other operations on the linked list implementation of a stack are provided.

Uploaded by

Mohamed Bilal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 13

SUBJECTSUBJECTCS8391CODECODE

DA
DATYPETTAASTRUCTURESSTRUTHE SUBJECT(CommonNAME toHERECSE & IT)

UNIT NO 1
LINEAR DATA STRUCTURES - STACKS, QUEUES

1.2 STACK ADT - OPERATIONS


III V LINKED LIST IMPLEMENTATION

CS8391
DATA STRUCTURES (Common to CSE & IT)
20ITPC301

DATA STRUCTURES (Common to CSE & IT)

STACK
20ITPC301
DATA STRUCTURES (Common to CSE & IT)

STACK
20ITPC301
DATA STRUCTURES (Common to CSE & IT)

What is a STACK ?

A stack is linear data structures, a container of elements that are inserted and removed according to the
last-in first-out (LIFO) principle.

A stack is a ordered list of elements of same data type

A stack is a Linear list


20ITPC301

DATA STRUCTURES (Common to CSE & IT)

Examples

Pile of books Bunch of cups


20ITPC301

DATA STRUCTURES (Common to CSE & IT)

LINKED LIST IMPLEMENTATION OF STACK?

In a stack all operation like insertion and deletion are performed at only one end called Top

• Instead of using array, we can also use linked list to implement stack.
• Linked list allocates the memory dynamically.
• However, time complexity in both the scenario is same for all the operations i.e. push, pop and peek.
• In linked list implementation of stack, the nodes are maintained non-contiguously in the memory.
• Each node contains a pointer to its immediate successor node in the stack.
• Stack is said to be overflown if the space left in the memory heap is not enough to create a node.
20ITPC301
DATA STRUCTURES (Common to CSE & IT)

STACK ADT – LINKED LIST


IMPLEMENTATION

In a stack all operation like insertion and deletion are


performed at only one end called Top
20ITPC301
DATA STRUCTURES (Common to CSE & IT)

STACK ADT – LINKED LIST IMPLEMENTATION – PUSH OPERATION


20ITPC301
DATA STRUCTURES (Common to CSE & IT)

STACK ADT – LINKED LIST IMPLEMENTATION

STEPS FOR POP OPERATION:


• Make a temporary node.
• Point this temporary node to the top of the stack
• Store the value of ‘data’ of this temporary node in a variable.
• Point the ‘top’ pointer to the node next to the current top node.
• Delete the temporary node using the ‘free’ function.
• Return the value stored in step 3.
20ITPC301
DATA STRUCTURES (Common to CSE & IT)

STACK ADT – LINKED LIST IMPLEMENTATION – POP OPERATION


CODE FOR POP OPERATION:
int pop()
{
node *tmp;
int n;
tmp = top;
n = tmp->data;
top = top->next;
free(tmp);
return n;
}
20ITPC301

DATA STRUCTURES (Common to CSE & IT)

STACK ADT – LINKED LIST IMPLEMENTATION – POP OPERATION

CODE FOR TOP OPERATION:


int Top()
{
return top->data;
}

int isempty()
{
return top==NULL;
}
20ITPC301

DATA STRUCTURES (Common to CSE & IT)

Linked list Implementation of Stack

void push(int value) void pop()


{ {
struct Node *newNode; if(top == NULL)
newNode = (struct printf("\nStack is Empty!!!\n");
Node*)malloc(sizeof(struct Node)); Else
newNode->data = value; {
if(top == NULL) printf("\n Deleted element: %d", temp->data);
newNode->next = struct Node *temp = top;
NULL; else top = temp->next;
newNode->next = free(temp);
top; top = }
newNode; }
printf("\n Insertion is Success!!!\n");
}
20ITPC301

DATA STRUCTURES (Common to CSE & IT)

Linked list Implementation of Stack

void display()
{
if(top == NULL)
printf("\nStack is
Empty!!!\n"); else{
struct Node *temp = top;
while(temp->next != NULL){

printf("%d--->",temp->data);

temp = temp -> next;


}
printf("%d--->NULL",temp->data);
}
}

You might also like