STACK Represetation Using Array

Insert an element into a stack (Push operation)

[Link](x)
Algo

1. begin
2. if top = n then stack full
3. top = top + 1
4. stack (top) : = item;
5. end

implementation of push algorithm in C language

1. void push (int val,int n) //n is size of the stack

2. {
3. if (top == n )
4. printf("\n Overflow");
5. else
6. {
7. top = top +1;
8. stack[top] = val;
9. }
10. }

Deletion of an element from a stack (Pop operation)

[Link]()
Algorithm:

1. begin
2. if top = 0 then stack empty;
3. item := stack(top);
4. top = top - 1;
5. end;
 Implementation of POP algorithm using C language

1. int pop ()
2. {
3. if(top == -1)
4. {
5. printf("Underflow");
6. return 0;
7. }
8. else
9. {
10. return stack[top - - ];
11. }
}

Visiting each element of the stack (Peek operation)

Algorithm

[Link] (STACK, TOP)

1. Begin
2. if top = -1 then stack empty
3. item = stack[top]
4. return item
5. End

Implementation of Peek algorithm in C language

1. int peek()
2. {
3. if (top == -1)
4. {
5. printf("Underflow");
6. return 0;
7. }
8. else
9. {
10. return stack [top];
11. }
12. }

C Program:

C program

1. #include <stdio.h>
2. int stack[100],i,j,choice=0,n,top=-1;
3. void push();
4. void pop();
5. void show();
6. void main ()
7. {
8.
9. printf("Enter the number of elements in the stack ");
10. scanf("%d",&n);
11. printf("*********Stack operations using array*********");
12.
13. printf("\n----------------------------------------------\n");
14. while(choice != 4)
15. {
16. printf("Chose one from the below options...\n");
17. printf("\[Link]\[Link]\[Link]\[Link]");
18. printf("\n Enter your choice \n");
19. scanf("%d",&choice);
20. switch(choice)
21. {
22. case 1:
23. {
24. push();
25. break;
26. }
27. case 2:
28. {
29. pop();
30. break;
31. }
32. case 3:
33. {
34. show();
35. break;
36. }
37. case 4:
38. {
39. printf("Exiting....");
40. break;
41. }
42. default:
43. {
44. printf("Please Enter valid choice ");
45. }
46. };
47. }
48. }
49.
50. void push ()
51. {
52. int val;
53. if (top == n )
54. printf("\n Overflow");
55. else
56. {
57. printf("Enter the value?");
58. scanf("%d",&val);
59. top = top +1;
60. stack[top] = val;
61. }
62. }
63.
64. void pop ()
65. {
66. if(top == -1)
67. printf("Underflow");
68. else
69. top = top -1;
70. }
71. void show()
72. {
73. for (i=top;i>=0;i--)
74. {
75. printf("%d\n",stack[i]);
76. }
77. if(top == -1)
78. {
79. printf("Stack is empty");
80. }
81. }

Linked list implementation of stack

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.
The top most node in the stack always contains null in its address field. Lets discuss the way in
which, each operation is performed in linked list implementation of stack.

Adding a node to the stack (Push operation)

Algorithm:

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). 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.

Time Complexity : o(1)

 C implementation :

1. void push ()
2. {
3. int val;
4. struct node *ptr =(struct node*)malloc(sizeof(struct node));
5. if(ptr == NULL)
6. {
7. printf("not able to push the element");
8. }
9. else
10. {
11. printf("Enter the value");
12. scanf("%d",&val);
13. if(head==NULL)
14. {
15. ptr->val = val;
16. ptr -> next = NULL;
17. head=ptr;
18. }
19. else
20. {
21. ptr->val = val;
22. ptr->next = head;
23. head=ptr;
24.
25. }
26. printf("Item pushed");
27.
28. }
29. }
Deleting a node from the stack (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 :

30. 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.
31. 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)

C implementation

1. void pop()
2. {
3. int item;
4. struct node *ptr;
5. if (head == NULL)
6. {
7. printf("Underflow");
8. }
9. else
10. {
11. item = head->val;
12. ptr = head;
13. head = head->next;
14. free(ptr);
15. printf("Item popped");
16.
17. }
18. }
Display the nodes (Traversing)

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.

Copy the head pointer into a temporary pointer.

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

Time Complexity : o(n)

C Implementation

1. void display()
2. {
3. int i;
4. struct node *ptr;
5. ptr=head;
6. if(ptr == NULL)
7. {
8. printf("Stack is empty\n");
9. }
10. else
11. {
12. printf("Printing Stack elements \n");
13. while(ptr!=NULL)
14. {
15. printf("%d\n",ptr->val);
16. ptr = ptr->next;
17. }
18. }
19. }

program in C implementing all the stack operations using linked list :

1. #include <stdio.h>
2. #include <stdlib.h>
3. void push();
4. void pop();
5. void display();
6. struct node
7. {
8. int val;
9. struct node *next;
10. };
11. struct node *head;
12.
13. void main ()
14. {
15. int choice=0;
16. printf("\n*********Stack operations using linked list*********\n");
17. printf("\n----------------------------------------------\n");
18. while(choice != 4)
19. {
20. printf("\n\nChose one from the below options...\n");
21. printf("\[Link]\[Link]\[Link]\[Link]");
22. printf("\n Enter your choice \n");
23. scanf("%d",&choice);
24. switch(choice)
25. {
26. case 1:
27. {
28. push();
29. break;
30. }
31. case 2:
32. {
33. pop();
34. break;
35. }
36. case 3:
37. {
38. display();
39. break;
40. }
41. case 4:
42. {
43. printf("Exiting....");
44. break;
45. }
46. default:
47. {
48. printf("Please Enter valid choice ");
49. }
50. };
51. }
52. }
53. void push ()
54. {
55. int val;
56. struct node *ptr = (struct node*)malloc(sizeof(struct node));
57. if(ptr == NULL)
58. {
59. printf("not able to push the element");
60. }
61. else
62. {
63. printf("Enter the value");
64. scanf("%d",&val);
65. if(head==NULL)
66. {
67. ptr->val = val;
68. ptr -> next = NULL;
69. head=ptr;
70. }
71. else
72. {
73. ptr->val = val;
74. ptr->next = head;
75. head=ptr;
76.
77. }
78. printf("Item pushed");
79.
80. }
81. }
82.
83. void pop()
84. {
85. int item;
86. struct node *ptr;
87. if (head == NULL)
88. {
89. printf("Underflow");
90. }
91. else
92. {
93. item = head->val;
94. ptr = head;
95. head = head->next;
96. free(ptr);
 97. printf("Item popped");
98.
99. }
100. }
101. void display()
102. {
103. int i;
104. struct node *ptr;
105. ptr=head;
106. if(ptr == NULL)
107. {
108. printf("Stack is empty\n");
109. }
110. else
111. {
112. printf("Printing Stack elements \n");
113. while(ptr!=NULL)
114. {
115. printf("%d\n",ptr->val);
116. ptr = ptr->next;
117. }
118. }
119. }

Application of Stack Data Structure:

 Function calls and recursion: When a function is called, the current state of the program
is pushed onto the stack. When the function returns, the state is popped from the stack to
resume the previous function’s execution.
 Undo/Redo operations: The undo-redo feature in various applications uses stacks to keep
track of the previous actions. Each time an action is performed, it is pushed onto the stack.
To undo the action, the top element of the stack is popped, and the reverse operation is
performed.
 Expression evaluation: Stack data structure is used to evaluate expressions in infix,
postfix, and prefix notations. Operators and operands are pushed onto the stack, and
operations are performed based on the stack’s top elements.
 Browser history: Web browsers use stacks to keep track of the web pages you visit. Each
time you visit a new page, the URL is pushed onto the stack, and when you hit the back
button, the previous URL is popped from the stack.
 Balanced Parentheses: Stack data structure is used to check if parentheses are balanced or
not. An opening parenthesis is pushed onto the stack, and a closing parenthesis is popped
from the stack. If the stack is empty at the end of the expression, the parentheses are
balanced.
 Backtracking Algorithms: The backtracking algorithm uses stacks to keep track of the
states of the problem-solving process. The current state is pushed onto the stack, and when
the algorithm backtracks, the previous state is popped from the stack.
Application of Stack in real life:
 CD/DVD stand.
 Stack of books in a book shop.
 Call center systems.
 Undo and Redo mechanism in text editors.
 The history of a web browser is stored in the form of a stack.
 Call logs, E-mails, and Google photos in any gallery are also stored in form of a stack.
 YouTube downloads and Notifications are also shown in LIFO format(the latest appears
first ).
 Allocation of memory by an operating system while executing a process.
Advantages of Stack:
 Easy implementation: Stack data structure is easy to implement using arrays or linked
lists, and its operations are simple to understand and implement.
 Efficient memory utilization: Stack uses a contiguous block of memory, making it more
efficient in memory utilization as compared to other data structures.
 Fast access time: Stack data structure provides fast access time for adding and removing
elements as the elements are added and removed from the top of the stack.
 Helps in function calls: Stack data structure is used to store function calls and their states,
which helps in the efficient implementation of recursive function calls.
 Supports backtracking: Stack data structure supports backtracking algorithms, which are
used in problem-solving to explore all possible solutions by storing the previous states.
 Used in Compiler Design: Stack data structure is used in compiler design for parsing and
syntax analysis of programming languages.
 Enables undo/redo operations: Stack data structure is used to enable undo and redo
operations in various applications like text editors, graphic design tools, and software
development environments.
Disadvantages of Stack:
 Limited capacity: Stack data structure has a limited capacity as it can only hold a fixed
number of elements. If the stack becomes full, adding new elements may result in stack
overflow, leading to the loss of data.
 No random access: Stack data structure does not allow for random access to its elements,
and it only allows for adding and removing elements from the top of the stack. To access an
element in the middle of the stack, all the elements above it must be removed.
 Memory management: Stack data structure uses a contiguous block of memory, which
can result in memory fragmentation if elements are added and removed frequently.
 Not suitable for certain applications: Stack data structure is not suitable for applications
that require accessing elements in the middle of the stack, like searching or sorting
algorithms.
 Stack overflow and underflow: Stack data structure can result in stack overflow if too
many elements are pushed onto the stack, and it can result in stack underflow if too many
elements are popped from the stack.
 Recursive function calls limitations: While stack data structure supports recursive
function calls, too many recursive function calls can lead to stack overflow, resulting in the
termination of the program.

Infix ,Prefix and Postfix in Stack

Infix Notation

When the operator is written in between the operands, then it is known as infix notation.
Operand does not have to be always a constant or a variable; it can also be an expression itself.

For example,

(p + q) * (r + s)

Prefix Notation:
Prefix notation is the notation in which operators are placed before the corresponding operands
in the expression.
Example:
Infix notation: A + B
Prefix notation: +AB
Postfix Notation:
Postfix notation is the notation in which operators are placed after the corresponding operands
in the expression.
Example:
Infix notation: A + B
Postfix notation: AB+
 Infix to Postfix Conversion using Stack in C

Conversion of Infix to Postfix can be done using stack. The stack is used to reverse the order of
operators. Stack stores the operator because it can not be added to the postfix expression until
both of its operands are added. The precedence of the operator also matters while converting
infix to postfix using stack, which we will discuss in the algorithm. Note: Parentheses are used to
override the precedence of operators, and they can be nested parentheses that need to be
evaluated from inner to outer.

Algorithm for Conversion of Infix to Postfix using Stack in C

Here are the steps of the algorithm to convert Infix to postfix using stack in C:

 Scan all the symbols one by one from left to right in the given Infix Expression.

 If the reading symbol is an operand, then immediately append it to the Postfix Expression.

 If the reading symbol is left parenthesis ‘( ‘, then Push it onto the Stack.

 If the reading symbol is right parenthesis ‘)’, then Pop all the contents of the stack until the
respective left parenthesis is popped and append each popped symbol to Postfix Expression.

 If the reading symbol is an operator (+, –, *, /), then Push it onto the Stack. However, first, pop
the operators which are already on the stack that have higher or equal precedence than the
current operator and append them to the postfix. If an open parenthesis is there on top of the
stack then push the operator into the stack.
 If the input is over, pop all the remaining symbols from the stack and append them to the postfix.

Example:-

Convert into infix to postfix

1.(A+B/C*(D+C)-F)

Output: ABC/DE+*+F-

2.A + (B * C - (D / E ^ F ) * G ) * H

Output: ABC*DEF^/G * - H * +

Recursion and Iteration

both repeatedly execute the set of instructions. Recursion occurs when a statement in a
function calls itself repeatedly. The iteration occurs when a loop repeatedly executes until the
controlling condition becomes false. The basic difference between recursion and iteration is
that recursion is a process always applied to a function and iteration is applied to the set of
instructions which we want to be executed repeatedly.

What is Recursion?
Recursion is defined as a process in which a function calls itself repeatedly. Recursion
uses selection structure. If the recursion step does not reduce the problem in a manner that
converges on some condition, called base condition, then an infinite recursion occurs. An
infinite recursion can crash the system. Recursion terminates when a base case is recognized.

Because of the overhead of maintaining the stack, the recursion process is usually slower than
iteration. Also, recursion uses more memory than iteration. However, it makes the code smaller,
thus it is an amazing technique that makes it easier to read and write the code.

What is Iteration?
Iteration is defined as the repetition of computational or mathematical procedure that continues
until the controlling condition becomes false. It uses repetition structure. If the loop condition
test never becomes false, then an infinite loop occurs with iteration. This infinite looping uses
CPU cycles repeatedly. An iteration terminates when the loop condition fails. Iteration
consumes less memory, but makes the code longer which is difficult to read and write

Property Recursion Iteration

A set of instructions repeatedly

Function calls itself.
Definition executed.

Application For functions. For loops.

Through base case, where there When the termination condition for the
Termination will be no function call. iterator ceases to be satisfied.

Used when code size needs to be Used when time complexity needs to be
small, and time complexity is not balanced against an expanded code
Usage an issue. size.

Code Size Smaller code size Larger Code Size.

Relatively lower time

Very high(generally exponential)
Time complexity(generally polynomial-
time complexity.
Complexity logarithmic).

Space The space complexity is higher

Space complexity is lower.
Complexity than iterations.

Here the stack is used to store

local variables when the function Stack is not used.
Stack is called.

Execution is slow since it has the

Normally, it is faster than recursion as
overhead of maintaining and
it doesn’t utilize the stack.
Speed updating the stack.

Recursion uses more memory as Iteration uses less memory as compared

Memory compared to iteration. to recursion.

Overhead Possesses overhead of repeated No overhead as there are no function

function calls. calls in iteration.
 If the recursive function does not
If the control condition of the iteration
meet to a termination condition or
statement never becomes false or the
the base case is not defined or is
control variable does not reach the
never reached then it leads to a
termination value, then it will cause
stack overflow error and there is
infinite loop. On the infinite loop, it
Infinite a chance that the an system may
uses the CPU cycles again and again.
Repetition crash in infinite recursion.

Tower of Hanoi, is a mathematical puzzle which consists of three towers (pegs) and more than
one rings is as depicted −

These rings are of different sizes and stacked upon in an ascending order, i.e. the smaller one sits
over the larger one. There are other variations of the puzzle where the number of disks increase,
but the tower count remains the same.

Rules

The mission is to move all the disks to some another tower without violating the sequence of
arrangement. A few rules to be followed for Tower of Hanoi are −

 Only one disk can be moved among the towers at any given time.
 Only the "top" disk can be removed.
 No large disk can sit over a small disk.

Following is an animated representation of solving a Tower of Hanoi puzzle with three disks.
Tower of Hanoi puzzle with n disks can be solved in minimum 2n−1 steps. This presentation
shows that a puzzle with 3 disks has taken 23 - 1 = 7 steps.

Algorithm

To write an algorithm for Tower of Hanoi, first we need to learn how to solve this problem with
lesser amount of disks, say → 1 or 2. We mark three towers with
name, source, destination and aux (only to help moving the disks). If we have only one disk,
then it can easily be moved from source to destination peg.

If we have 2 disks −

 First, we move the smaller (top) disk to aux peg.

 Then, we move the larger (bottom) disk to destination peg.
 And finally, we move the smaller disk from aux to destination peg.

So now, we are in a position to design an algorithm for Tower of Hanoi with more than two
disks. We divide the stack of disks in two parts. The largest disk (nth disk) is in one part and all
other (n-1) disks are in the second part.

Our ultimate aim is to move disk n from source to destination and then put all other (n1) disks
onto it. We can imagine to apply the same in a recursive way for all given set of disks.
The steps to follow are −

Step 1 − Move n-1 disks from source to aux

Step 2 − Move nth disk from source to dest
Step 3 − Move n-1 disks from aux to dest

A recursive algorithm for Tower of Hanoi can be

driven as follows −
START
Procedure Hanoi(disk, source, dest, aux)

IF disk == 1, THEN
move disk from source to dest
ELSE
Hanoi(disk - 1, source, aux, dest) // Step 1
move disk from source to dest // Step 2
Hanoi(disk - 1, aux, dest, source) // Step 3
END IF

END Procedure
STOP
Example