Stack As An Array:3/2/2020 Hello Friends, Are stacks stacking tension in your mind? Are you also suffering to learn its concepts and understand program? You are in the right place. Welcome to my second blog and here we will discuss about Stack and how can it be implemented using arrays. So let's begin. We will first discuss concept of stack, followed by operations that can be performed on stack and finally a C Program illustrating stack and operations. Definition of Stack: It is a special type of data structure where elements can be inserted and deleted from the same end. This is the definition you will find in most books. Let's understand this definition. Just visualize a stack of plates placed in a cupboard. Do you take out the last plate 1st for use? The answer is NO. You take the plate kept on top. But did you kept that plate first? The answer is again NO. You kept that plate last in the stack and the last plate in the stack 1st. The similar thing is applied on Stack data structure. You insert elements from one end only and take out elements from the same end. So it is not possible to remove or add elements randomly. We need to add elements at the end and remove elements from the same end. So stack is also said to follow the "LIFO->Last In First Out" concept. For a better understanding here are 2 animations for you. 1st one shows how elements are added to stack and 2nd one shows how elements are deleted from a stack. For now just focus on animation and avoid any technical term that you cannot understand. We will come to them in just a moment. Insertion of Elements in a Stack: Deletion of element from a stack: Hope the above animations drew a clear image of what a stack is in your mind. Now we will discuss about the operations that we can perform on a stack. So we can perform 2 operations on a stack. They are PUSH and POP. The operation of adding elements to the stack is called PUSH. The operation of removing elements to the stack is called POP. So the 1st animation depicts PUSH operation and 2nd animation depicts POP operation. Now a question may arise to your mind that what is the Top. We will discuss about it up next. Now we will be coming on a point that how to code Stack using array. We all know that array can be declared in a program in 2 ways. 1st way is to use dynamic memory location i.e using malloc() function or by declaring any size and ask the user for number of elements and then use those spaces only and rest of the space remains unused. I used the 1st way in my 1st Blog. Its a bit complex. So for simplicity I will use the 2nd way in this program. We know that in arrays we can easily insert and delete elements according to our convenience. So to implement stack we will declare a variable named Top (Usually used for convenience. You may use different name), that will take care of insertion and deletion. So now lets discuss the program. Suppose the stack has n elements. When stack will be empty,Top's value will be equal to -1 and when stack is full, Top's value will be equal to (n-1). Initially Top is initialized -1. I prefer declaring it globally so any change anywhere in program gets reflected every where and we don't need to update its value everywhere. Program for implementation of stack: The program for stack will have 4 functions. They are:
Element can be inserted in the stack only if there is any empty space in the stack. If the stack is already full then no elements can be inserted. When the stack is already full but still user wants to insert elements, such a situation is called "Overflow" condition. If there is space then element gets inserted one by one and Top gets shifted (we can say that it points to the currently inserted element)(refer animation 1 for better understanding). Here is the snippet of PUSH function. POP Function: Elements can be deleted from a stack only if there are elements present for deletion. What if the stack is empty but still the user attempts to delete any element? Such a situation is called "Underflow" condition. If the elements are present then deletion takes place successfully and Top shifts one by one (we can say that Top points to the element which was just below the deleted element)(refer animation 2 for better understanding). Here is a snippet of POP Function. Display Function: We use a function that displays the stack. The function contains a for loop that runs from 0 up to Top and displays elements of stack. Here's the snippet of the function. Main Function: I have use menu driven approach. Other approach may also be used. Here's the snippet of main function. Here are some snaps of output. Link_to_code: https://github.com/souravsaraf2000/Stack-as-an-array So here we discussed Stack and implemented it using arrays. Hope you liked the content. Please let me know about your views in the comment. Also share the blog with your friends. Hit the like button below if you liked the content. Always open for corrections. You can contact me using my email ID or LinkedIn or Using contact form. Thank You. Animation Credits: tutorial4us.com
8 Comments
Introduction to Data Structures:29/1/2020 Hello Friends, Welcome to my blog. Here I will be discussing some concepts about Data Structures and I will try to provide you a clear idea about concepts. I will assume you to have knowledge of basic C programming language. Here, in this blog we will revise some important concepts required to learn DS. They are Arrays, Structures and Pointers. So Let's begin with Arrays. ARRAYS: Definition of arrays: Arrays are a collection of similar data types (i.e int,float,double,long and long double). They are also defined as contiguous memory locations that can store similar type of data. Declaring an array: As we all know, to use any variable in C programming language, we first need to declare them. Similarly we also need to declare an array as well. It is as simple as declaring a variable but with its size i.e we need to specify the number of locations we need. Don't get confused. Here is an example for you. Example: int arr[10]; The above statement means that we declared an array named "arr" that is capable to storing "10" "integer type" elements. Initialising an array: There are 2 ways in which an array can be initialised. 1> Hard Coding(Not Recommended) 2> Using for loop I will be showing you both the ways. 1> Hard Coding: This way is not recommended because it makes the program monotonous and not a generalized one. Example: int arr[ ]={1,2,3,4,5,6,7,8,9,10}; This way should be used when the elements of the array is known. 2> Using for loop: In this method we take input from the user of the program and assign elements to the array using for loop. Example: int arr[10],i; printf("Enter Elements Of The Array="); for(i=0;i<10;i++) { scanf("%d",&arr[i]); } Accessing Elements of Array: As already mentioned that arrays are contiguous memory locations. So we can easy access its elements using indexes. If there are 10 memory blocks in an array then the 1st block will have index 0 and last block will have index 9. And that's why we begin the for loop from 0 every time and upto less than or equal to (n-1) or less than n (refer the above example) so that n blocks can be accessed. We will discuss a lot more about arrays in the up-coming blogs. Structures: Definition_of_Structures: Structures are collection of similar (all elements are of similar data type) or dissimilar (all elements are of different data types) type of data members under one name. Structures are basically used to declare user defined data types i.e a data type according to users convenience. Declaring a Structure: We can declare a structure using the "struct" keyword followed by structure name and the members of the structures within { } followed by a ; (semi colon). It is declared globally. Example: struct right_angled_triangle { int base; int perpendicular; int hypotenuse; }; Memory Allocation and variable declaration: Does the above structure gets memory? The answer is "NO". The reason is we just declared a data type named right_angled_triangle and no variable of such data type is created. A better interpretation could be like if we write "int x;" in a program, it means that a variable x is declare of type int. Similarly right_angled_triangle is a data type whose definition is given by structure. It is very similar to writing int. Hope it is clear. Now if we declare a variable of type struct right_angled_triangle then it will get 6 bytes (considering int takes 2 bytes of memory) of memory as there are 3 integers in the structure. Example: struct right_angled_triangle r; r will get 6 bytes of memory. Accessing structure variables: Structure variables can be accessed using dot operator("."). Example: r.base=3; r.perpendicular=4; r.hypotenuse=5; Pointers: Now this is a topic where I found many people get confused and fear the topic a lot. This is a very important topic for DS and one should have very good grip on pointers. I will try to provide clear conception about the topic. Definition of Pointers: Pointers are address variables that can store address of other variables so that the variable can be accessed indirectly. Now a question may arise that why do we need to access variables indirectly. Here's the answer. Why should we use pointers?: Suppose there is a variable or file in "HEAP MEMORY" and we need to access it in our program. But according to C programming methodology we cannot access anything in Heap Memory directly. Suppose there is a .txt file in Heap Memory and we need to print its contents. Then we need to use a pointer of "file type" to access the file. Suppose there is an integer variable in heap memory. Then we need to use a int pointer to access the variable. So pointer is very important for DS. Declaring a pointer:- Example: int *p; // Variable name preceded by a * makes it a pointer Initializing a Pointer(p):- Suppose we want p to store address of a variable "a". We can do it using & (address of operator). Example: int a=10; p=&a; Printing value of a using p:- We can print the value of a using the pointer p with the help of dereferencing operator(*). Example: printf("%d",*p); // Output will be 10 We need to get familiar with the syntax of pointers. Here is a program that creates a array in the heap memory(using dynamic memory allocation) and uses pointers to access elements of the array: Output of the above program: So in this blog we discussed and revised some concepts required for DS. Hope you liked the content. Please let me know about your views in the comment. Also share the blog with your friends. Hit the like button below if you liked the content. Always open for corrections. You can contact me using my email ID or LinkedIn or Using contact form.
Thank You. ArchivesCategories |