Data Structures (DS)
GTU # 3130702
Unit-2
Linear Data Structure
(Stack)
Stack Implementation
The major problem with the stack implemented using an array is, it works only for a fixed
number of data values.
That means the amount of data must be specified at the beginning of the implementation itself.
Stack implemented using an array is not suitable, when we don't know the size of data which
we are going to use.
A stack data structure can be implemented by using a linked list data structure.
Linked Stack Implementation
A stack data structure can be implemented by using a linked list data structure.
The stack implemented using linked list can work for an unlimited number of values. That
means, stack implemented using linked list works for the variable size of data.
In linked list implementation of a stack, every new element is inserted as 'top' element.
Whenever we want to remove an element from the stack, simply remove the node which is
pointed by 'top' by moving 'top' to its previous node in the list.
The next field of the first element must be always NULL.
Linked Stack
Example
Procedure : PUSH (value)
push(value) - Inserting an element into the Stack
Use the following steps to insert a new node into the stack...
Step 1 - Create a newNode with given value.
Step 2 - Check whether stack is Empty (top == NULL)
Step 3 - If it is Empty, then set newNode → next = NULL.
Step 4 - If it is Not Empty, then set newNode → next = top.
Step 5 - Finally, set top = newNode.
Function : POP ()
pop() - Deleting an Element from a Stack
Use the following steps to delete a node from the stack...
Step 1 - Check whether stack is Empty (top == NULL).
Step 2 - If it is Empty, then display "Stack is Empty! Deletion is not possible!" and terminate
the function
Step 3 - If it is Not Empty, then define a Node pointer 'temp' and set it to 'top'.
Step 4 - Then set 'top = top → next'.
Step 5 - Finally, delete 'temp'. (free(temp)).
Procedure: DISPLAY()
display() - Displaying stack of elements
Use the following steps to display the elements (nodes) of a stack...
Step 1 - Check whether stack is Empty (top == NULL).
Step 2 - If it is Empty, then display 'Stack is Empty!!!' and terminate the function.
Step 3 - If it is Not Empty, then define a Node pointer 'temp' and initialize with top.
Step 4 - Display 'temp → data --->' and move it to the next node. Repeat the same
until temp reaches to the first node in the stack. (temp → next != NULL).
Step 5 - Finally! Display 'temp → data ---> NULL'.
Linked Stack Implementation
//Linked Stack ADT
#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
int data;
struct Node *next;
}stack;
stack *top = NULL;
void push(int);
void pop();
void display();
PUSH
void push(int value)
{
stack *new;
new = (stack*)malloc(sizeof(stack));
newNode->data = value;
if(top == NULL)
new->next = NULL;
else
new->next = top;
top = new;
printf("\nInsertion is Success!!!\n");
}
POP
void pop()
{
if(top == NULL)
printf("Stack is Empty!!");
else{
stack *temp = top;
printf("Deleted element: %d", temp->data);
top = temp->next;
free(temp);
}
}
display
void display()
{
stack *temp;
if(top == NULL)
printf("Stack is Empty!");
else{
temp = top;
while(temp != NULL){
printf("%d--->",temp->data);
temp = temp -> next;
}
}
}
main handler function
int main()
{
int choice, value;
printf(": Stack using Linked List ::");
while(1){
printf("****** MENU ******");
printf("1. Push\n2. Pop\n3. Display\n4. Exit");
printf("Enter your choice: ");
scanf("%d",&choice);
switch(choice){
case 1: printf("Enter the value to be insert: ");
scanf("%d", &value);
push(value);
break;
case 2: pop(); break;
case 3: display(); break;
case 4: exit(0);
default: printf("Wrong selection!!! Please try again!");
}
} return 0;
}