write in the form of comments ramu@dayina
A stack is a linear data structure,
collection of items of the same type.
Stack follows the Last In First Out
(LIFO) fashion wherein the last element entered is the first one to be
popped out.
In stacks, the insertion and deletion of
elements happen only at one endpoint of it.
1. Operations
performed on Stacks
The following are the basic operations served
by the Stacks.
·
Push: This function adds an element to the top of the Stack.
·
Pop: This function removes the topmost element from the stack.
·
IsEmpty: Checks whether the stack is empty.
·
IsFull: Checks whether the stack is full.
·
Top: Displays the topmost element of the stack.
2. Working of Stacks
Initially, we set a pointer Peek/Top to keep
the track of the topmost item in the stack.
Initialize the stack to -1. Then, we check
whether the stack is empty through the comparison of Peek to -1 i.e. Top
== -1
As we add the elements to the stack, the
position of the Peek element keeps updating every time.
As soon as we pop or delete an item from the
set of inputs, the top-most element gets deleted and thus the value of Peek/Top
gets reduced.
3. Implementing Stack
in C
Stacks can be represented using structures, pointers, arrays or linked lists.
Here, We have implemented stacks using arrays in C.
#include<stdio.h>
#include<stdlib.h>
#define Size 4
int Top=-1, inp_array[Size];
void Push();
void Pop();
void show();
int main()
{
int choice;
while(1)
{
printf("\nOperations performed by Stack");
printf("\n1.Push the element\n2.Pop the element\n3.Show\n4.End");
printf("\n\nEnter the choice:");
scanf("%d",&choice);
switch(choice)
{
case 1: Push();
break;
case 2: Pop();
break;
case 3: show();
break;
case 4: exit(0);
default: printf("\nInvalid choice!!");
}
}
}
void Push()
{
int x;
if(Top==Size-1)
{
printf("\nOverflow!!");
}
else
{
printf("\nEnter element to be inserted to the stack:");
scanf("%d",&x);
Top=Top+1;
inp_array[Top]=x;
}
}
void Pop()
{
if(Top==-1)
{
printf("\nUnderflow!!");
}
else
{
printf("\nPopped element: %d",inp_array[Top]);
Top=Top-1;
}
}
void show()
{
if(Top==-1)
{
printf("\nUnderflow!!");
}
else
{
printf("\nElements present in the stack: \n");
for(int i=Top;i>=0;--i)
printf("%d\n",inp_array[i]);
}
}
Output:-
Operations performed by Stack
1.Push the element
2.Pop the element
3.Show
4.End
Enter the choice:1
Enter element to be inserted to the stack:10
Operations performed by Stack
1.Push the element
2.Pop the element
3.Show
4.End
Enter the choice:3
Elements present in the stack:
10
Operations performed by Stack
1.Push the element
2.Pop the element
3.Show
4.End
Enter the choice:2
Popped element: 10
Operations performed by Stack
1.Push the element
2.Pop the element
3.Show
4.End
Enter the choice:3
Underflow!!
4. Time Complexity of
Stack Operations
As mentioned above, only a single element can
be accessed at a time in Stacks.
While performing push() and pop() operations
on the stack, it takes O(1) time.
5. Applications of
Stack
As soon as the compiler encounters a function
call, it gets pushed into the stack.
In the case of nested functions, the inner
functions get executed before the outer functions. This is totally managed by
stacks.
The Stack is used to solve a few of the
general problems like:
1.
Tower of Hanoi
2.
N queens problem
3.
Infix to prefix
conversion, etc.
6. Conclusion
Thus, in this article, we have understood the
concept of Stack data structure and its implementation using Arrays in C.
కామెంట్లు లేవు:
కామెంట్ను పోస్ట్ చేయండి