Implement a stack using singly linked list

1. In linked list implementation of stack, the nodes are maintained non-

contiguously in the memory.
2. Each node contains a pointer to its immediate successor node in the stack.
3. Stack is said to be overflown if the space left in the memory heap is not
enough to create a node.

 In the stack Implementation, a stack contains a top pointer. which is the

“head” of the stack where pushing and popping items happens at the
head of the list.
 The first node has a null in the link field and second node-link has the
first node address in the link field and so on and the last node address is
in the “top” pointer.
 The main advantage of using a linked list over arrays is that it is
possible to implement a stack that can shrink or grow as much as
needed.
 Using an array will put a restriction on the maximum capacity of the
array which can lead to stack overflow.
 Here each new node will be dynamically allocated. so overflow is not
possible.
Stack Operations:
 push(): Insert a new element into the stack i.e just insert a new element at
the beginning of the linked list.
 pop(): Return the top element of the Stack i.e simply delete the first
element from the linked list.
 peek(): Return the top element.
 display(): Print all elements in Stack.
 Push Operation:
Adding a node to the stack is referred to as push operation. Pushing an element
to a stack in linked list implementation is different from that of an array
implementation. In order to push an element onto the stack, the following steps
are involved.

1. Create a node first and allocate memory to it.

2. If the list is empty then the item is to be pushed as the start node of the list.
This includes assigning value to the data part of the node and assign null
to the address part of the node.
3. If there are some nodes in the list already, then we have to add the new
element in the beginning of the list (to not violate the property of the stack).
4. For this purpose, assign the address of the starting element to the address
field of the new node and make the new node, the starting node of the list.

ALGORITHM:
 Initialise a node
 Update the value of that node by data i.e. node->data = data
 Now link this node to the top of the linked list
 And update top pointer to the current node
Time Complexity : o(1)
 Pop Operation:
 Deleting a node from the top of stack is referred to as pop operation.
 Deleting a node from the linked list implementation of stack is different
from that in the array implementation.
 In order to pop an element from the stack, we need to follow the
following steps :

1. Check for the underflow condition: The underflow condition occurs

when we try to pop from an already empty stack. The stack will be empty
if the head pointer of the list points to null.
2. Adjust the head pointer accordingly: In stack, the elements are
popped only from one end, therefore, the value stored in the head
pointer must be deleted and the node must be freed. The next node of
the head node now becomes the head node.

Time Complexity : o(n)

ALGORITHM:
 First Check whether there is any node present in the linked list or not, if not
then return
 Otherwise make pointer let say temp to the top node and move forward the
top node by 1 step
 Now free this temp node

 Peek Operation:
 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.
  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.

ALGORITHM:
 Check if there is any node present or not, if not then return.
 Otherwise return the value of top node of the linked list

 Display Operation:
Displaying all the nodes of a stack needs traversing all the nodes of the
linked list organized in the form of stack. For this purpose, we need to
follow the following steps.

1. Copy the head pointer into a temporary pointer.

2. Move the temporary pointer through all the nodes of the list and print
the value field attached to every node.

Time Complexity : o(n)

ALGORITHM:
 Take a temp node and initialize it with top pointer
 Now start traversing temp till it encounters NULL
 Simultaneously print the value of the temp node

 EXPLAIN THE PROGRAM FOR LINKED LIST IMPLEMENTATION

OF A STACK WITH VARIOUS OPERATIONS.

PROGRAM-1
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

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

void push(int data)

{
struct node* newNode;
newNode=malloc(sizeof(newNode));
if(newNode==NULL)
{
printf("Stack Overflow");
exit(1);
}
newNode->data=data;
newNode->link=NULL;

newNode->link=top;
top=newNode;
}

int pop()
{
struct node* temp;
int val;
if(isEmpty())
{
printf("Stack Underflow");
exit(1);
}
temp=top;
val=temp->data;
top=top->link;
free(temp);
temp=NULL;
return val;
}

int peek()
{
if(isEmpty())
{
printf("Stack Underflow");
exit(1);
}
return top->data;
}

void print()
{
struct node* temp;
temp=top;
if(isEmpty())
{
printf("Stack Underflow");
exit(1);
}
printf("The stack elements are:");
while(temp)
{
printf("%d",temp->data)
temp=temp->link;
}
printf("\n");
}

int main()
{
int choice,data;
clrscr();
while(1)
{
printf("\n Operations on stacks using Linked List");
printf("\n 1.push \n 2.pop \n 3.print the top element \n 4.print all elements \n
5.Quit \n");
printf("\n please enter your choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1:printf("\n Enter the elements to be pushed ");
scanf("%d",&data);
push(data);
 break;
case 2: data=pop();
printf("\n Deleted elements is %d \n ",data);
break;
case 3: printf("\n The topmost element of the stack is %d \n ",data);
break;
case 4:print();
break;
case 5:exit(1);
default:printf("\n Wrong choice \n");
}
}
return 0;
}

PROGRAM-2:

/*stack program using linked list*/

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

struct node{
int info;
struct node *ptr;
} *top,*top1,*temp;

int count=0;
void push(int data)
{
if(top==NULL)
{
top=(struct node*)malloc(1*sizeof(struct node));
top->ptr=NULL;
top->info=data;
}
else
{
temp=(struct node*)malloc(1*sizeof(struct node));
temp->ptr=top;
temp->info=data;
top=temp;
}
count++;
printf("\n node is inserted \n \n");
}

int pop()
{
top1=top;
if(top1==NULL)
{
printf("\n Stack Underflow");
return -1;
}
else
{
top1=top1->ptr;
int popped =top->info;
free(top);
top=top1;
count--;
printf("\n item popped : %d",popped);
return popped;
}
}

void display()
{
top1=top;
if(top1==NULL)
{
printf("\n Stack Underfloe \n");
}
printf("\nThe stack is \n");
while(top!=NULL)
{
printf("%d--->",top1->info);
top1=top1->ptr;
}
printf("NULL \n\n");
}
int main()
{
int choice,value;
clrscr();
printf("\n Implementation of stack using Linked List \n");
while(1)
{
printf("\n 1.Push \n 2.Pop \n 3.Display \n 4.Exit \n");
printf("\n Enter your choice");
scanf("%d",&choice);

switch(choice){
case 1:printf("\n Enter the value to insert:\n");
scanf("%d",&value);
push(value);
break;
case 2:printf("\n popped element is %d\n",pop());
break;
case 3:display();
break;
case 4:exit(0);
break;
printf("\n wrong choice \n");
}
}
}

 List the Applications of Stacks:

 Function calls: Stacks are used to keep track of the return addresses of
function calls, allowing the program to return to the correct location after a
function has finished executing.

 Recursion: Stacks are used to store the local variables and return addresses
of recursive function calls, allowing the program to keep track of the
current state of the recursion.

 Expression evaluation: Stacks are used to evaluate expressions in postfix

notation (Reverse Polish Notation).

 Syntax parsing: Stacks are used to check the validity of syntax in

programming languages and other formal languages.

 Memory management: Stacks are used to allocate and manage memory in

some operating systems and programming languages.
Notations for Arithmetic Expression
There are three notations to represent an arithmetic expression:

o Infix Notation
o Prefix Notation
o Postfix Notation

Infix Notation

The infix notation is a convenient way of writing an expression in which each

operator is placed between the operands. Infix expressions can be parenthesized
or unparenthesized depending upon the problem requirement.
Example: A + B, (C - D) etc.

All these expressions are in infix notation because the operator comes between
the operands.

Prefix Notation

The prefix notation places the operator before the operands. This notation was
introduced by the Polish mathematician and hence often referred to as polish
notation.

Example: + A B, -CD etc.

All these expressions are in prefix notation because the operator comes before the
operands.

Postfix Notation

The postfix notation places the operator after the operands. This notation is just
the reverse of Polish notation and also known as Reverse Polish notation.

Example: AB +, CD+, etc.

All these expressions are in postfix notation because the operator comes after the
operands.
The precedence rules for the five basic arithmetic operators are:

Associativity Precedence
Operators

^ exponentiation Right to left Highest followed by *Multiplication and

/division

*Multiplication, Left to right Highest followed by + addition and -

/division subtraction

+ addition, - Left to right lowest

subtraction

Conversion of Arithmetic Expression into various Notations:

Infix Notation Prefix Notation Postfix Notation

A*B *AB AB*

(A+B)/C /+ ABC AB+C/

(A*B) + (D-C) +*AB - DC AB*DC-+

 CONVERT INFIX EXPRESSION TO POSTFIX

EXPRESSION:
Example:
Infix expression: The expression of the form “a operator b” (a + b) i.e.,

when an operator is in-between every pair of operands.

Syntax of infix notation is given below:

<operand> <operator> <operand>

Postfix expression: The expression of the form “a b operator” (ab+) i.e.,

When every pair of operands is followed by an operator.
Examples:
Input: A + B * C + D
Output: ABC*+D+

Operators Symbols

Parenthesis ( ), {}, [ ]

Exponents ^

Multiplication and Division *, /

Addition and Subtraction +,-

Input: ((A + B) – C * (D / E)) + F

Output: AB+CDE/*-F+

To convert infix expression to postfix expression, use the stack data structure.
Scan the infix expression from left to right. Whenever we get an operand, add
it to the postfix expression and if we get an operator or parenthesis add it to
the stack by maintaining their precedence.

Rules for the conversion from infix to postfix expression

1. Print the operand as they arrive.

2. If the stack is empty or contains a left parenthesis on top, push the incoming
operator on to the stack.
3. If the incoming symbol is '(', push it on to the stack.
4. If the incoming symbol is ')', pop the stack and print the operators until the
left parenthesis is found.
5. If the incoming symbol has higher precedence than the top of the stack,
push it on the stack.
 6. If the incoming symbol has lower precedence than the top of the stack, pop
and print the top of the stack. Then test the incoming operator against the
new top of the stack.
7. If the incoming operator has the same precedence with the top of the stack
then use the associativity rules. If the associativity is from left to right then
pop and print the top of the stack then push the incoming operator. If the
associativity is from right to left then push the incoming operator.
8. At the end of the expression, pop and print all the operators of the stack.

(OR)

EXAMPLE:
Consider the infix expression exp = “a+b*c+d”
and the infix expression is scanned using the iterator i, which is initialized as i
= 0.

1st Step: Here i = 0 and exp[i] = ‘a’ i.e., an operand. So add this in the postfix
expression. Therefore, postfix = “a”.

 2nd Step: Here i = 1 and exp[i] = ‘+’ i.e., an operator. Push this into
the stack. postfix = “a” and stack = {+}.
 3rd Step: Now i = 2 and exp[i] = ‘b’ i.e., an operand. So add this in the
postfix expression. postfix = “ab” and stack = {+}.

 4th Step: Now i = 3 and exp[i] = ‘*’ i.e., an operator. Push this into the
stack. postfix = “ab” and stack = {+, *}.
 5th Step: Now i = 4 and exp[i] = ‘c’ i.e., an operand. Add this in the
postfix expression. postfix = “abc” and stack = {+, *}.

 6th Step: Now i = 5 and exp[i] = ‘+’ i.e., an operator. The topmost
element of the stack has higher precedence. So pop until the stack
becomes empty or the top element has less precedence. ‘*’ is popped
and added in postfix. So postfix = “abc*” and stack = {+}.

 Now top element is ‘+‘ that also doesn’t have less precedence. Pop
it. postfix = “abc*+”.
Now stack is empty. So push ‘+’ in the stack. stack = {+}.

 7th Step: Now i = 6 and exp[i] = ‘d’ i.e., an operand. Add this in the
postfix expression. postfix = “abc*+d”.
 Final Step: Now no element is left. So empty the stack and add it in the
postfix expression. postfix = “abc*+d+”.
Infix expression: K + L - M*N + (O^P) * W/U/V * T + Q

Input Expression Stack Postfix Expression

K K

+ + K

L + KL

- - K L+

M - K L+ M

* -* K L+ M

N -* KL+MN

+ + K L + M N*
K L + M N* -

( +( K L + M N *-

O +( KL+MN*-O

^ +(^ K L + M N* - O

P +(^ K L + M N* - O P

) + K L + M N* - O P ^

* +* K L + M N* - O P ^

W +* K L + M N* - O P ^ W

/ +/ K L + M N* - O P ^ W *

U +/ K L + M N* - O P ^W*U

/ +/ K L + M N* - O P ^W*U/

V +/ KL + MN*-OP^W*U/V

* +* KL+MN*-OP^W*U/V/
 T +* KL+MN*-OP^W*U/V/T

+ + KL+MN*-OP^W*U/V/T*
KL+MN*-OP^W*U/V/T*+

Q + KL+MN*-OP^W*U/V/T*Q

KL+MN*-OP^W*U/V/T*+Q+

The final postfix expression of infix expression(K + L - M*N + (O^P) * W/U/V

* T + Q) is KL+MN*-OP^W*U/V/T*+Q+.

 EXPLAIN THE PROGRAM FOR CONVERSION OF INFIX

EXPRESSION TO POSTFIX EXPRESSION
PROGRAM:
#include<stdio.h>
#include<ctype.h>

char stack[100];
int top = -1;

void push(char x)
{
stack[++top] = x;
}

char pop()
{
if(top == -1)
return -1;
else
 return stack[top--];
}

int priority(char x)
{
if(x == '(')
return 0;
if(x == '+' || x == '-')
return 1;
if(x == '*' || x == '/')
return 2;
return 0;
}

int main()
{
char exp[100];
char *e, x;
printf("Enter the expression : ");
scanf("%s",exp);
printf("\n");
e = exp;

while(*e != '\0')
{
if(isalnum(*e))
printf("%c ",*e);
 else if(*e == '(')
push(*e);
else if(*e == ')')
{
while((x = pop()) != '(')
printf("%c ", x);
}
else
{
while(priority(stack[top]) >= priority(*e))
printf("%c ",pop());
push(*e);
}
e++;
}

while(top != -1)
{
printf("%c ",pop());
}return 0;
}

OUTPUT:1
Enter the expression:a+b*c
abc*+
OUTPUT :2
Enter the expression:((4+8)(6-5))/((3-2)(2+2))
48+65–32–22+/

 EVALUATION OF POSTFIX EXPRESSION:

Postfix expression: The expression of the form “a b operator” (ab+) i.e.,
when a pair of operands is followed by an operator.
Examples:
Input: str = “2 3 1 * + 9 -“
Output: -4
Explanation: If the expression is converted into an infix expression, it will be
2 + (3 * 1) – 9 = 5 – 9 = -4.
Input: str = “100 200 + 2 / 5 * 7 +”
Output: 757

Evaluating Postfix expression:

Stack is the ideal data structure to evaluate the postfix expression because the top
element is always the most recent operand. The next element on the Stack is the
second most recent operand to be operated on.

Before evaluating the postfix expression, the following conditions must be

checked. If any one of the conditions fails, the postfix expression is invalid.

o When an operator encounters the scanning process, the Stack must contain
a pair of operands or intermediate results previously calculated.
o When an expression has been completely evaluated, the Stack must contain
exactly one value.

Example:

Now let us consider the following infix expression 2 * (4+3) - 5.

The following step illustrates how this postfix expression is evaluated.

Consider the expression: exp = “2 3 1 * + 9 -“

 Scan 2, it’s a number, So push it into stack. Stack contains ‘2’.

 Scan 3, again a number, push it to stack, stack now contains ‘2 3’ (from

bottom to top)

 Scan 1, again a number, push it to stack, stack now contains ‘2 3 1’

 Scan *, it’s an operator. Pop two operands from stack, apply the * operator
on operands. We get 3*1 which results in 3. We push the result 3 to stack.
The stack now becomes ‘2 3’.

 Scan +, it’s an operator. Pop two operands from stack, apply the +
operator on operands. We get 3 + 2 which results in 5. We push the
result 5 to stack. The stack now becomes ‘5’.
 Scan 9, it’s a number. So we push it to the stack. The stack now becomes ‘5
9’.

 Scan -, it’s an operator, pop two operands from stack, apply the – operator
on operands, we get 5 – 9 which results in -4. We push the result -4 to the
stack. The stack now becomes ‘-4’.
 There are no more elements to scan, we return the top element from the
stack (which is the only element left in a stack).
So the result becomes -4.

STEPS TO EVALUATE POSTFIX EXPRESSION:

Follow the steps mentioned below to evaluate postfix expression using stack:
 Create a stack to store operands (or values).
 Scan the given expression from left to right and do the following for every
scanned element.
o If the element is a number, push it into the stack.
o If the element is an operator, pop operands for the operator from
the stack. Evaluate the operator and push the result back to the
stack.
 When the expression is ended, the number in the stack is the final answer.

EXAMPLE:

38+98/-

1. Read the expression from left to right, initialize a stack with the same
length as the expression.
2. If the element encountered is an operand, push it into the stack.
3. If the element encountered is an operator, pop two operands a and b from
the stack, apply the operator (b operator a) and push the result back into
the stack.
 4. In the above example: 3 8 + 9 8 / -

Input Stack Postfix evaluation

234*+ empty Push 2 into stack

34*+ 2 Push 3 into stack

4*+ 32 Push 4 into stack

*+ 432 Pop 4 & pop 3 from stack and do 3 *4 , push 12 into stack

+ 12 2 Pop 12 & Pop 2 from stack do 2 + 12, push 14 into stack

14

Input Stack Postfix evaluation

34*25*+ empty Push 3 into stack

4*25*+ 3 Push 4 into stack

*25*+ 43 Pop 4 & pop 3 from stack do 3*4, Push 12

25*+ 12 Push 2 into stack

5*+ 2 12 Push 5 into stack

*+ 5 2 12 Pop 5, Pop 2 from stack do 2*5, Push 10 into stack

+ 10 12 Pop 10 & Pop 12 from stack do 12 + 10, push 22 into stack

22

WRITE A PROGRAM FOR EVALUATING POSTFIX EXPRESSION

PROGRAM:
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// Stack implementation
int stack[MAX_SIZE];
int top = -1;
void push(int item) {
if (top >= MAX_SIZE - 1) {
printf("Stack Overflow\n");
return;
}
top++;
stack[top] = item;
}
int pop() {
if (top < 0) {
printf("Stack Underflow\n");
return -1;
}
int item = stack[top];
top--;
return item;
}
int is_operator(char symbol) {
if (symbol == '+' || symbol == '-' || symbol == '*' || symbol == '/') {
return 1;
}
return 0;
}
int evaluate(char* expression) {
int i = 0;
char symbol = expression[i];
int operand1, operand2, result;

while (symbol != '\0') {

if (symbol >= '0' && symbol <= '9') {
int num = symbol - '0';
push(num);
}
else if (is_operator(symbol)) {
operand2 = pop();
operand1 = pop();
switch(symbol) {
case '+': result = operand1 + operand2; break;
case '-': result = operand1 - operand2; break;
case '*': result = operand1 * operand2; break;
case '/': result = operand1 / operand2; break;
}
push(result);
}
i++;
symbol = expression[i];
}
result = pop();
return result;
}
int main() {
char expression[] = "5 6 7 + * 8 -";
int result = evaluate(expression);
printf("Result= %d\n", result);
return 0;
}

OUTPUT:
Result=57