Data Structures- Leture 4

                                                  Data Structures
                                     Lecture 4
Stack Representation

Let us start with how stacks are represented. So stacks are represented with a node in the linked list with the node containing data. That is what is to be represented and link pointing to the next node. And the also you have and access to a stack throw a node. Which is designated to a stack and also maintain the count the no. of elements of the stack. Now first think we going doing is create a stack. To creating a stack, you have to first dynamically the allocate a stack. Who size is equal to the size of the stack and if the stack top is equal to null. When that is what you are doing. To the initialize the top and we are also since creating the stack. And any top initialize equal to be null and count to be equal to zero. You are not a actually create a node. This is first step in creating a stack. So once you created a stack we went to do the operation from stack. Important operation has push already seen push operation. This is if you look at linked list representation of stack. In the push operation similar to inserting a node in the front of a list. Because already operations are done with a stack at the top of the you can access the stack accessed to throw only the top. Insertion and deletion when you represent a stack as the linked list is in the front. So here. Same as inserting a new element to the list before the first. So let us assume that this is the element. You want to insert and this is the previous stack. So previous stack has this is the count and is the top. So top is pointing to the first element in the stack. Are you wanted to insert the new element? First to create an element for the node. And this is the address of the node. And this is containing the data red and pointer next. So that’s what is available. When you are going to insert this into the stack. It’s come like this. Now this is Pnew and which know this is address of this. You create next. Change the next pointer to point to the address of blue. And change to things top to point to address of red and increment the count be equal to 3. So this is insertion of push operation. We don’t call it insert in stacks. We call it push operation. Push into the stack. Which is represented as a linked list. So this is the push operation. The code for the push operation so first thing will you do introduce create a node. In that node you creating a node. You have get it from the allocated area. If there is no allocated area. That is can’t get a new node. You can’t insert. Once you got that. In the new position you put data. Pointed to that data whatever to insert. And you make the pointer of the new location of the new node. That is to be created.
Pointed to original stack top. And now change the stack top pointed to the new pointer implement top to the point to the new node. And increment the count of the stack by one. And return one. And Return one this is indicated. So this is what we do for insertion into a stack. As we consider to this is very similar to the insertion into the front of the linked list. Now let us look at the next operation of stack. Which is pop. Pop is to delete the element and as you know you can only the delete element from top of the stack. That is the constraint that you have on stack. So this is the same as the removing first element from a linked list. So what you have to do is. This is an original stack. Now the only element you can delete or remove from the stack from and do the pop operation. In this element. No other element can remove. So what you do is. You make the pop. Now point to blue. Ok. That is it. So now you can access the stack. Only. Throw this. Now you have a node which is short of bankling. So this can be recycled. So you make a pointer to Point to this node. So that it can be recycled. So this is the pop operation. So the code for the pop operation. As follows. So you have a pointer to point to the node. Which you want to the return. And if the stack already discussed you want to a deletion and what do you want we consume must. First ensure that the data structure from which you want do the deletion. Is not empty. So that is what is doing here. Just checking the count what whether equal to zero. You saying that will return zero. Which means that is an underflow. That is no element. To be delete it. Otherwise you make this pointer to point to the original stack. This is for recycling purposes. And then what you do is. Make the stack top. Point to the new stack. Top and if free, dlt pointer. What do you going to doing here is, string is the node. That has been deleted. And decrement the stack count and return the value of stack. This is code for the pop stack. Both these cases the stack is represented using a linked list and these particular data structure is very useful. When we are doing for organizing the nodes in an allocated list. It is called allocation list. And these represented linked list. Who store all the nodes are has been deleted are when you want to delete. You store for recycling take allocated list. Which is represented as stack. When you want to insert to take a node from same allocated list. So the next stack top is already discussed before stack top doesn’t change stack at all. Just access the top element of the stack. So again if the count is only greater than zero. That mean stack doesn’t contain anything. Then just take out the pointer to the top element. Make that data to be returned in data pointer and return 1. If it is less than 0. That means no stack. So you return. So that is top. Know hearing to change of the list, this is can normal thing. And empty stack a stack count. So what you do here in. if the count is equal to zero then the return value. Otherwise the stack is not empty. This is a code for Boolean function. This is an empty stack. Which
is return value from the stack is empty. Which is value is false. The stack is not empty. This is return a count. So already maintain the count. There are implementation do not maintain count of the stack. Certain implementation you maintain count .so return stack. That is it. So the count can be equal to zero. The stack is empty. You can also check for full stack. This is assuming that u have decided that only so many nodes going to give for the stack. This is a stack. If you have stack full condition then malloc is failed. If malloc is failed, it means, you cannot there is no temporary node to be given to for the operation. In which case you have a return 1. So this is a full stack. Where you cannot, remember that in full stack condition checking whether there are nodes available for putting into the stack. If there are not saying full otherwise putting full. This is not like an array implementation already allocated the size of the stack. This is the destroying stack Destroying complete stack. So you want to delete all the nodes in the stack. So if the stack top is null it means already stack is empty. You don’t have after do any destroying. So if it is not null. Then you make delete pointer to point to the top of the stack top of the point to the next node and free delete pointer. You keep doing this. Till the stacks it will come. Come to the last node in the stack. The Stack is now empty then the destroy the head node. So free that and you return null. So this here having a by loop. Here this is the logic. Where you keep on deleting nodes of push. Popping of the nodes. Till start becomes. Now what you seen upto now is the some of the implementation of stacks. Where we look at linked list implementation of the stack. In this particular implementation of the stack. What you done is we are assume that you have a count. Also it is not necessary. So in case you don’t have a count the code has to be appropriately modified. Stack Applications Now let us go to next some of the application. Using stack. Very interesting applications. I said used in no.of places in computer science itself. For example, the stack is a particular specific data structure that is used for quick sort algorithm is a difficult data structure. It also used in other applications. Like very important application where you have to maintain the program counter and return address in the case of recursive calls in function calls. So this is very important data structure as well as computer science.is concerned. We are looking at 2 very different application. One is the depth first search. And one is the N_Queens problem. So let us first look at the depth first search. The depth first search actually backtracking type of concept. That it uses. And this backtracking type of concept we do use stack. Stack is a difficult data structure that is used for doing back tracking. So this problem as follows discover a part from start to goal and
the solution you have to go deep. If there is an unvisited neighbour go there then you retreat along the path to find an unvisited neighbour. The outcome is if there is a path from the stack to goal. DFs very finds such a path. So that is going to go deep and cannot enough to do. Go to DFS wise. That is an idea. So this is a difficult application of a stack. So let us soon given a tree and if you want to find the goal. So initialize to start at 1. That is pushed on to the stack. Then you go to two depth number. To get to the child. So push 2. When you push 5. 5 has no children so you go to the sibling with 6. Then Go to child 9. After then you don’t have anything. So Pop it up. Pop is 6 out. Then pop 5 out. Pop 2 out. When you go to the next child which is 3. Then you go to 7. Then you go to 10. That is depth first we go to 10. Now you have identifying the value. So that the path followed 1,2,5,6,9. Then back tracking up and then go to 1. Find the next child go down. Ok. That is the path followed by the depth first search. So let us algorithm for the DFS. So the stack is first initialized. And you stack the operation look at push start. Now while the stack is a not empty. This is keep track. You data in the top element. If it is the goal you just put access. If T has a unvisited neighbour. Choose an unvisited neighbour n. Mark N as visited and push n into the stack. Otherwise that is if doesn’t have a unvisited neighbour. When you backtrack take in the next node from the stack. Keep doing this. Till stack is empty. Are you reach the goal? So this is the DFS algorithm. Of course you searching the node in a algorithm you can also happen that here may be a failure. So this is a difficult application of stack. Where the stack is used to maintain the node. When we want to do the DFS algorithm. As specially backtracking algorithm. This is a difficult data structure that used many concept used back tracking. Also used stack is a basic data structure. For implementation purpose. N-Queens Problem
Now you going to look at what is the N_Queens problem? This is a difficult problem in artificial intelligence and the N_Queens problem is actually problem associated with the chess board. So in this lecture I will explain the problem and then how it is solved using the stack. OK. So first let us see what the problem is the NQueens problem can be defined as follows. It is a backtracking problem to solve the NQueens. Suppose you have 8 chess queens & and a chess board. Can the queens be placed on the board? So that no two queens are attacking each other? Now what do you mean by attacking. We will see that as we go long. So the problem is this. Two queens are not allowed in the same row, or in the same column. Or along the same diagonal. So that is the idea. So 2 queens are not allowed on the same row, and the same column, or along the same diagonal, the no.of queens and the size of the board can vary.
Normally use all this problem for the NQueens problem. We are going to take it can simple example and show you. But basically solve it for any queen. It after all chess board is the square. So you can 64 * 64. Where N = 64 and so on. So basically NQueens can be represented this way you consist of NQueens. And chess board that you have consist of N rows and N columns. So your aim is placed NQueens on the boards. Such that if you have a queen here. We don’t have queen anywhere here and also don’t have anywhere queen here. So you gone queen same diagonal on the same row, same columns, along this same row. That’s the problem so are idea is to try to find solution to this problem. The computer program to solve this problem. Program tries to find a way to place N queens on the N * N chess board. Following the instruction we already seen. Now comes the application of stack. We going to uses a stack to keep track of where each queen as already been placed. So first place a queen on the board. The position of the new queen is stored in a record which is placed in the stack. And also you have an integer variable to keep track of how many rows have been filled so for. So these are two things that a going to use keep track of how to place the NQueens. So the is how the program works you have take 4 */ 4 board in very simple example to show the how the program works and this is the no. of queens to be filed. Which is 4 and this is stack to be used. Stack contains record. Which gives the position of the queen. Which is 1,1 is the position 1,2 mean this 1, 4 means first row , 4th column and so on. And this is the variable. Which keeps track of how many queens have already been placed. OK. This is the way. This is the complete show. You have a N * N board. You have NQueens, you have a stack. Which give the position of queen and you have the no. of queens that mean placed directly as the program. Now let us start the program. So first you place 1 here. Then you come do this what happen so that is 1,1 has been placed here. Then you come here. Now can you placed queen here, you can’t the queen placed here. Because along it a same diagonal so the logic uses that you shift it once to the right and see whether breaks it in a rules now that is no queen along the column, that is no queen along the row, that is no queen along the diagonal. So this is allowed. Now you have a queen at 1,1 you have a queen at 2,3 and 2 have been filled. Now we are to place this. N row you can place it here. Can’t place it here. Because if it is in the diagonal. So what you do is? Go up here and place it here. can you place it here 3, 4 so 3 rd row, 4 Th column you can’t place it here. Because of the fact at that along diagonal. How the program works? When we run out of remove in or row, pop the stack,
reduce filled by 1 and continue working on the previous row. Let us look at that. What is mean these? When you can’t place, pop it off. Go to the previous row and you see whether place it along that. Along the right or left. You will see the logical as we see go long. Again I tell you. When we run out of room in a row, pop the stack, reduced filled by 1 and continue working on the previous row. Whatever you placed in the previous row, here are having so ok. That is what is happened here. This is r th position. We still have to queens 2. And reduced filled by 1. Now we continue working on row 2, shifting the queen to the right. Now instant have it here. We pop it up. And shifting the queen here. Now thus has to been incremented this position has no conflicts, so we can increase filled by 1, and move to row 3. So now we move to row 3. Ion row 3 what happens, we can’t place it here. Because diagonal. So placed it here. And then we go to 3 one. And this is the conflicts. We stack again first column conflicts. Second column that is no conflicts. So that is how we so along to the problem. You can work it on row. You see how 4 queens are filled. So the logical basically to be repeat. That is you take the row placed a queen there. Then you go to the next row place the queen there. When conflict arises. What you do is? You tried to push the queen to right. If it is possible and you know no conflicts arises. If you come across a conflict then you pop the top element from the stack. That’s you are a backtracking. You are not using that. Already placed it, removing from the stack. Which remove it. And try again to reworks on the previous row and that’s how you do the queen. Nqueens problem. So for are nqueens problem. Let us see this is slightly different from the problem. That mean normally used. We are going to first talk about the pseudo code.so here what we do is. We first initialize the stack. Which is date structure. We want to use. Keep track of artificians and we also place the first queen. Pushing its position onto the stack and setting filled it equal to be 0. This is pseudo code repeat these steps. If there are no conflicts in the queen then we do else if there is a conflict and there is room to shift the current queen right ward do it. Else if there is a conflict and there is no room to shift the current queen right ward then what we do. You have do keep on doing this. Repeat these steps. There are no conflicts increase filled by 1. If filled is now what then doing here and take this each of the steps and giving the details. If there are no conflicts with the queen what we do increase filled by 1. If filled row is now N. That means filled all the queens then the algorithm is over. Otherwise, move to the next row and place a queen in the first column. So that this steps is over. So what we and done is. We done this. If you take one queen ok. We are placed it the first in the row. We see there is a conflict. Then there is a conflict moving a right. If there is a conflict and
there is a room to shift the current queen rightward. Move the current queen rightward adjusting the record on top of the stack to indicate the new position. So, this is in the same row. Even that you can’t do. Position where you have can’t fill the there is conflict. Can’t move rightward and fill. Because there is a conflict again. If there is a conflict and there is a room to shift the current queen right ward. This is place to have do a back. So what you do. You keep popping the stack and reducing filled by 1. Until you reach a row where the queen can be shifted rightward. When you shift this queen right. Then what you doing is. What ever done before you backtracking. Can backtracking till you reach the position? Where you can have another alternative. Which is not placing that. But moving it to the right. If it is possible. So the movement to the right once step of the time. But you move one also. So that is the NQueen problem. By the NQueens problem is very challenging is that. We are actually redoing the work. We already done. So that we get the choice of what we doing actually in the algorithm is we first start with the easiest method. Placed the first row that we see. Then we keep on doing it till the and the second we can take is every ok. When I placed in that place there is a conflict. So I will let move right to see. If you move to right and see, fill a conflicts. So I will let more right to se. If you move to right and see, fill a conflicts. Only then I go back. And I check whether. What I will done can be changed so that’s can be accompanied. You can properly try thus for 6 * 6 or 4*4 on your own on. Similarly act how it works. That will be a good exercise for you. When you for you do understand. How the stack works and how backtracking algorithm work also. That is explain both the concept of backtracking as well as the application of stack to backtracking. Now let us look at some problems. Associated with stacks. There is know up to implementation of stack.

Read More

Data Structures - Lecture 3

 Data Structures - Lecture 3
Data Structure
Lecture 3
STACKS Stacks are a very important data structure and are necessary for implementing the logic behind many programmers. So let us look at start at the end of this lesson. we objective of this lesson this to introduce the concept of this stacks and then look at the operations of the stack and then the applications of the stacks these are thinks we going to talk about in this lesson before we go to on to the complete aspect of stacks as you know there are stacks every day in our life like stack of shirt, stack of books and stack of boxes and so on. As you see the idea is that normally when you take out the first shirt you take give be the top shirt of this stack and so on. So these are otherwise (57 sec) fall down and this catch in very carefully the same concept in applied to stacks in data structure. So this is the typical application of stack there will have stacks of book and stacks of coins at the same think represented in computer stack. Computer stack has gone to number of object set of placed one on top of other in a sense so another common linear data structure that I already talk to you about is stacks one you already seen its list and in one way the stack is nothing but the list but getter lot of restriction of how the list is used, then it became a stacks with the stack we have restricted to the access to the list to one end we take out the element from the stack using the pop element and we push element in to the stack using push operations. So the result of this restriction is that the list pile one on top of the other so basically talk about stacks we talk about when we what is call the last in first out policy. To get to the bottom item, we must first remove all the items above it another words so the behaviour is sometimes described as this is the policy we that talk about which is called is last in first out. So whenever you think of stacks you must think of it has last in first out whatever you put in last will be taken out first are so it’s called a LIFO and this is because I already told you that last item put in the stack the item removed first. So elements can be added and removed only at one end this end will call as the top of the stack with this stack the top item is always the last item to enter the stack and it is always the first item to leave the stack because no other items can be removed or added on to the stack without affecting the top element so let’s look at some terminology above the stack so the depth of stack is the number of elements it continues so suppose you have ten elements this stack it’s deep ten and you say that there are the depth is stack is ten and normally as obviously an empty stack is get a depth is zero. So why to be used a stack. Stacks provide a very efficient storage structure for manipulating data that is last in first out policy and stacks are often used as temporary storage to speculate the solution of a problem. So stack are restricted linear list as already told you of where
additions and detections are made only to the top and what happened is because of this specialization are restrictions that we do on the stack we can implement the stack using link list and we can also implement the stack using arrays and we think of ways in which in efficiency of the implementation can be improved. So as before you just seen basically what I stack data structure is you must remember that stack data structure is that restricted types of list and its follows the last in first out policy all access to the stack is to through the pointer call pop and through the top you can instead element and delete elements and the last item which has to be which has been instead the first item that is to be removed. Now let us look at all the operations that you can do on stacks. So first operations the do on the stacks .what is called a max item. Max that is nothing but the maximum number of items that would be on a stack. Now before you going to details about this that what the meaning of max item depends on the implementation of the stack so if it is arrays implementation. You already discuss array implementation they will be maximum size of the array and that will be the maximum number of elements you can put in the stack but how many elements has actually we put is the max item and item type can vary it can single and simple integer are we can a structure and we can as we saw list san be any data item they others are make empty that is an operation that make a stack completely and you can also have a Boolean operation call is empty that is to test whether the stack is empty or not similarly you can have Boolean is full the test whether the stack is full this actually make sense only you can talking about array implementation and next you have push (X,S) this is to add push an element X to the top of a stack S and then this is the function as this is the adds X to the top of the stack and the pre-condition is that in order to push in a element to the stack. The stack should not be full and the post condition is at after the push operation the element X becomes the top elements of the stack next you have pop S this is nothing but up to delete element an a stack it’s call pop the top most elements of from the stack and the functions of obviously its remove the element stack and return the item and the pre-condition has for any deletion operation for that can be matters this stack should next be a empty it has to be initialize and it has cannot be empty if it’s empty the pop operation is become un defined the post condition is that the top element would have remove from the stack and copy of item will be available and the top has been modified then you have something call has top S the stack S has it is hear is axis to the top most element of the stack hear no change occurs to the stack and only the top most element you will get the value of the element that’s it . So let us go little more in details about the operation of the stack so you have first the push. Push is add and item and the problem here is that you can over flow suppose you say the stack in contain ten item and it’s already full within ten item then you try to added another element eleventh element then the stack is overflow condition occurred this is the only for the array implementation and for the pop element you remove an element you can have already total you can have a underflow and the stack top is what the top is stack so this is the pop operation you end element and this is the stack pop operation where you take out it so let’s take this more in details so you have the take this more in details so you have the data that you want to push on the stack this is the initial stack of the stack. So for example the stack has to element and assuming the stack starts with the top is equal to one here you have the top is equal to two so now when you sit what happened is this the element data is pushed on to like this the top increment is one and the element stack size increases. Now let us assume we want explain the pop operation as you already know it moves data element from top of the stack initially the stack has three element and top now points to three when you do a pop operation there is no questions of which element to delete you can only delete the top most element the way the stack is defined so what you do you give the pop operation the top most element is deleted that is return and top reduces by one so this is the pop operation. Then look at this operation this is the stack top operation you don’t have any change in the stack. Stack has three element and also a three element top value here is three here top value is three and only think is you are able to access the element and value is given out please not when I say top is equal to 1, 2, 3 am assuming the array on the stack is which is told in a array and top start from one it’s not necessary you can start stack from hundred you can array location hundred and you can also store stack in link list then the meaning of this is different it here is explain it’s so you understand what the operation is this so let’s look at simple figure here if you look here in this step one you have the empty stack and given a data that you want to push on the stack now what happens here you will note the tope is equal to zero and the stack is empty now incremented top by one and pushing into green into the stack now this is the new condition is the stack is end. Then with that you add another element which is blue here so now top becomes two and belay pushed on the stack this is the condition of the stack after the second push operation then what you do you go to the see the pop given the stack of the stack if I just give pop there is no questions of which element is pop because pop the top most element so what happened after the pop operation blue comes out and this is new condition of the stack where top is been decremented by the one and blue is no longer present in the stack then next let’s see if you want added another element that element is push this is similar to at do it here and top increments by one then doing a stack top operation here what happens the state a stack is before and after the operation is same but only think if you can access the element then this operation and this operation is the same you just removed a element and here also you doing pop operation . you see here that is green has been removed that is top most element
from the stack has been remove the stack is empty now if you give pop operation there is error in the condition because the stack has is empty .so let us look at stack as an abstract data type so that means we are not bother about the implementation we going to using this stack so basically for any stack. Whatever the implementation the following at the operation of function that associated with the stack so one is create this means you just create an a empty stack for the implementation then the push you seen in of about the push. Push means added an element top of the stack then you have pop which means pop an element from the top of the stack you don’t have to specify the element because only think at pop from the stack is top element then stack top which you already defined that is you are accessing the top element of the stack no changing in the stack that is the top remains in the same number of element in the stack remains the same then you can also have full condition the question mark that we put here is you cannot check a full condition when you do a link list implementation of a stack because you can keep an adding notes dynamically but fill make sense in the stack is implemented as an a array and then empty is when the stack is element that is does not contain any element so this is the stack in empty condition so you can just look at this small data structure of this so you have a external interface you have a data structure and can have the data here so this is the data you want to input in to the stack this is just giving feeling of what is available outside. The outside is when you doing push you have indicate which element it is X. which stack you want to put it and similarly when you defining the stack you have to also know the access point that is top of the stack so one typical application of a stack is the famous parenthesis matching or matching of brackets so what it do here this you don’t have a matching parenthesis here so what it do you input when you see the traverses list from this corner when you see the bracket you put it in the stack then you see the other bracket . Put it the stack then you see an a just pass it don’t be anything you see plus B don’t be anything then you see the closing bracket. So you look at this stack and C whether whatever you have top of the stack matches this if it matches you removed that so now you left with is one bracket one that we put here then you see a divide sign don’t be anything just pass it C. don’t be anything then you finished you come to the end of the expression when you come to the end of the expression if it was matching expression. You should have add the stack is empty unfortunately now the stack is contain the single bracket so you know that the equation has not brackets have not been matched if you look at this same think you can do it surffency you see that this you will put on the stack. Then here you will you put on the stack again are left with closing bracket that is not matching so here are matching we a put in this on the stack then you putting a open parenthesis and the stack then you have a matching closing parenthesis which will cancel each other that will left with in
open parenthesis here you will left with the closing parenthesis but however you do that always you should have the stack is empty then only it’s matched now in this example you take on simple example there is only one type of bracket you can have any type you can have square bracket and check the corresponding matching. 

 

So you can actually do parenthesis matching automatically using the stack data structure for any type of complex expression so as we already saw the stack ADT can have several implementations. Implementations may be different but implementation details are be hidden and the interface function have to be the same and most application programmes should not see any difference just because using array implementation arm using a stack implementation. So let us first look at the stack implementation using an array so stack is stored as an array when you stored stack is an array immediately it means that the number of element has to be allocated that is how many element this stack in cold so I can here constantly look at the stack as we done before so I have defined something called as defined stack array and then have a something called as stack max. Stack max is maximum number of elements that I can store is physical array and top tells be the top element you can actually not have the count also the doesn’t matter but stack array, stack max, and top has to be defined. If you want to define a stack using array so implementing stack using array. It’s a simple implementation. The size of the stack must be determined when a stack object is declared space is wasted if we use less elements suppose you have a stack you declared it have hundred elements and usually the stack within ten and fifteen then you wasting the space and we cannot push the more element and then the array can hold. So this is the typical definition of stack of integers in an array implementation. So what you doing here is we are declaring the array call stack array and then this is the number of element at count then stack max this is equivalent to what we saw before for this . We are defining the structure so this is the maximum element and this top is the index of the top element. So all of them are integers in this case so first step here is creating a stack so you will say the create a stack with maximum elements ok so if the stack is equal to null check as stack is empty you return a null otherwise you going to now you going to allocate the stack. So first what we do you initialize the top of the stack to be minas one and count is equal to zero remember this is stack which is empty. So doesn’t have anything. So you can defined the top of many way in this implementation have a initialize. The stack to be minas one and stack count be equal to zero that is same and then stack max has been initialize to the maximum. Number of elements that we want the stack hold and the stack array that is the complete array defined as allocate maximum element into size of the element size. So if stacks stack array is equal to null. Then that means free all free the stacks always return the null so it done here this you creates at a stack which called stack array which has top is equal to minas one
count is equal to zero and the stack max equal maximum number of element. So next let as look at the push operation so the push stack you have when you remember when I told you told that you have a push stack operation you have two think as to define one is the stack array which is the array in which you want to push into the next is data element that we want to push so first for any push operation infect this is two five any in session operation you have first check whether there is place to instant the element in other words. So for that we are doing a stack check full stack check. So here what you doing is if the count of the number of elements is equal to the maximum number of elements is stack can hold then we are returning zero let us it is over flow and the number of elements in this stack equal to the maximum number you can hold and you cannot add any more elements otherwise when you come out this it means that you have to place the hold elements but in case what you do is you increment the count so the number of elements in the stack increases by one you increment pop by one because now want to create to a place pointed at to this top, there you want to inset the element and then what you do you with array at the position calls top you inset the elements that you want to inset and you return one . just this indicate that the push operation has been success if it already full then you did have return zero which means that there is the problem there is an error and this condition the error is a overfull. So this is how you do please note here we are first incrementing talk to create place and then we are putting the element into the top position so next let look at pop operation again as you know in any deletion operation you should have something to delete so in deletion operation you will get an under flow the same is true for stack. So here what you do you given a stack given data output pointer this is the data you going to output and given a stack you can you did not have the as in input parameter you can gives the stack and you can delete from that but here want to get out what is top on the stack for that’s why having the extra parameter some pop operation implementation do not look at this is a separate parameter inside the pop operation. One of the example. We saw people we did not have to parameters for the pop – operation. So here what you do this please remember this is array implementations? So what you do is you first. Check whether stack is empty if it is empty then you cannot do a deletion operation, became you don’t know anything to delete. So you getting underflow condition otherwise what you do is you have to take out the them the list of the stack so what you do the access is top element of the stack and take it out is the variable call data output points and decrement the count by one because round in the count number of element is decreased and decrement top also by one because previously whatever top is pointing to is now a empty so end don’t want to access is you will decrement all and return one indicate one it is successful operation this is the top operation this function retrieve the data is the top of the stack without
changing the stack so again as we already saw pre-conditions stack is pointer to the stack and post return one its success zero is under flow so have what you do is we have the stack again and this is the output pointer as we did in the pop operation so it the count is greater than zero than only you can do the operation. If it is can then zero you don’t have to access at all because these stack in empty you don’t have a element so it is next zero that this then element greater than zero that is element so you just take out the elements not take out you just access the element but remember no top changing nothing change is the count does not decrease nothing happens only think is accessing the top element so hear after the top operation this stack remain same is as already told you and returning zero this return zero is if not able to do the operation because of count being not greater than zero which mean that’s the stack is this is the condition check whether the stack is empty as next so the pre-condition is stack is pointer to the stack and post condition is if returns one its empty and zero is there is data is this stack so here what you do is again the input the stack and you that’s the structure stack. If the count is equal to zero that means is an empty stack. You just Boolean you will return the value that is true value similarly full this function determine the stack is full so fully detained as heat full ok heap full for latter so pre stack is pointed to the stack head note suppose if return one heap for stack is full and zero is heap as room what you do here is this is full stack condition again we have the complete structure now here because its and array implementation then you know the stack is full then the count is equal to these stack max so if count is equal to these stack max so if the count is equal to the maximum element the stack in held then we know that the stack hen full then you return the value now Growable tray – based stack this is the slightly difference diversion of what will apposing to say In a push operation, when the array is full, instead of throwing an exception, we can replace the array with a larger one. How large should the new array be? Incremental strategy: increase the size by a constant C. doubling strategy, double the size, what you mean by here is we docent usually know cannot predict how much the size of stack will be now the problem here is that you have if you put stack is 1000 elements are using one 10 or 15 eliminating wasting are memory resources are then have you put is or 10 elements you against to 20 or 30 elements then you concisely you will getting a stack full condition. So one we doing this is have global array stating what will you do is if you get stack full condition that point you reallocated larger array and then put all the stack elements is to that array so this is not a very simple operation. This is changing of elements from one array to other bus assume that you can do that but two strategists of how the largers array allocated how much of how much should be one think you going to suppose the original stack size is 10 and you a have stack full condition you can increased by constancy size 5 and every time to get a stack full condition keep
increment, increasing it by 5 please not this depends of the explication purely on the application. How you have a doubling stratarge Initially I will put 10 I will act put 10 and then came now will have stack size of 20 again can put 20 and so on. So this is a predict. So depending of the application you do this now we go the next type of implementation plus please not but when I said we going of global array after you stack full condition is array happen when you allocate a larger array that is the lot of completion on work needed transfer this array implementation of next array implementation. So this not to travel operation so this not to say that global array is a solution to the problem of using of array stack operator so next implementation in the link list implementation. So here what you do is you have to understand the concept of an abstract data type again you already seeing this and you need to see understand nested implementation and you need to see some application of link list so every data of course touch a goes also top link list implementation of stack. So this is the typical link list implementation of a stack so here you see that this is conceptual view here the conceptual view of whether you implement of the stack using link list are whether implement the stack using array conceptual view is same but when you look at this now what you have the bottom most element will have the link pointer to be equal to zero and then you have the next element pointing to this element pointing to this, this element pointing to this and count is the number of element in the stack before and top now giving the address of the top most pointer, this link is given the address of the next top most the bottom most element. The address link will be equal to zero this is the link list implementation of the stack. Now let’s look at this is no count this is the top this is the before you create a stack now look here you are incremented. This is the a creating a empty stack so what happened this you have count equal to zero and top pointing to null still the stack is empty you just created a stack now let us look at push operation now what happens the count is zero the top most equal to zero now what am doing am creating a node to put green this is the same operation what we saw when we did link list implementation of a stack so what happens after this green I have to change the address of this stack from null to the address of this node and this next here has to be null so next is again a push operation now this has to be now node has to be created and please note that is new node will come here because now this is we comes the bottom most node and the top has point to the most reason node and top most node now what will have to increment the count by two this buy will point to the new node and the next of the new node will pointed to the previous top so this is what happens is the blue has to be removed so now top will point to green again and blue will be removed it’s blue will be entered here and blue will be removed from there so if you want to distributed stack what you do this you make a count zero. If you don’t have any point of from top address of

top immediately stack not accessible all so disturbed the stack. So here you have two data structure that we using two modes that using one this is stack head other this stack node so this stack will have a count and top which is count an integer and top is a doubt pointer this will have a data type and this will be a link which is again note point this is similar to structure that we used for this but here the operation are restricted I already told you that again this data type can be a single data type or have a large record whatever so the key data structure of this structure that used this CR again a node with key integer data and struck node which is an address and you can also have stack and the stack is represented by a count and the stack node pointing to the top so let us look at operation a stack so when you create a stack you have a pointer to the stack and you have allocate this equal to be size of the stack. So if stack equal to null then you initialize the top and have you going to this is creation of the stack remember and you already seeing here how do you create a stack what do you this to put the count equal to zero and top equal to null that is exactly what you a doing here putting the top equal to null and count is equal to zero and the address of the stack is return this is the allocating the size of the I mean allocating stack to be dynamic allocation of a node.

Read More

Data Structures - Lecture 2

Data structure Lecture -2

Arrays We are going to look at two implementation of list. Two important implementation of list. One is array and another is using linked list. So first let us look at implementation of list using arrays. Before we are going to that we have to know what an arrays? Array is usually associated with pair of values an index and a value. An array is a sequence of indexed items. For example when I say the first element it is the index is one. And then the element is also fix as five are something other. If I say 10, A[10] it means that the 10th index is 10 and the element value of the whatever the element there will come out. So associated with each index there is a value, and normally an important constraint of arrays is that the length of the array has to be fixed. Before the array is created and it is implemented using consecutive memory. Now one important thing that we have do known is that when we represent list using arrays, the list is logically continuous as well as physically continuous in other words the elements of the array are stored in consecutive memory location. When an array is created consecutive memory blocks is allocated dynamically to store the values of the element of the array. So if we take an example. 

Let us assume that the array consist of 0,1,2,3,4. You will see that, here we assume that 2 address location are used represent one element of the array. So 1 to 2 it’s contains 0. 1,2,3,0 contains 1. The index will be 1,2,3,4,5. This is contiguous memory location that allocated. Normally, we talk about an array. The indices an array range from the lower index bound normally 0 most programming languages. Through the higher index bound n-1. It means that you can represent N element using the particular array. Any items of the array can be access directly by just giving its index. So when you say A[1] you can access the first element. When you say A[5], you can access the fifth element and time complexity of accessing an element is 0 of the order of 1, which means error if its 1000th the element array. If you say A[1000] you can access directly to the 1000th element. So operation you do create and initialize the length is a find the number of elements in the array and insertion & deletion. So given an array like a left to right. You can insert of a value and a particular location. If necessary we have to shift the elements. Insertion and deletion is most time consuming and inefficient operations. When you represent list using an array. Now search on the other hand is the most efficient operation that we do.

When you represent the list using an array. List in finding an any particular element from the array from the list represented using an array. So array is a basic data structure and it can store any type of an element. It can be integer array. It can be character array, an array consisting of nodes which is the structure. An important application of array is the representation of polynomial. Polynomial is consist of an exponent, degree of the polynomial is largest exponent. So this is particular polynomial you can represent the array. For example 3 has one data element and 20 as other data element and +2 is other, +5 is other ad so on. Linked List 1 Another representation of list, please remember talking about list. And how do an implement the list? The first type saw as an array. The second type is a linked list. Now if you look here. This is typical representation of list. Which is represented to a linked list. Now you see that bat, cat, sat, vat is a list and logically they are next to each other or sequential. But, when you use a linked list to represent a list the memory are physically they or not adjacent to each other, they are only logically adjacent to each other. For example, bat can be stored a 1000 location cat can be stored that 200 location. For example, sat at 600 location and vat at 2000. In spite of that because of this link points that address of the next element and because of this they become logically adjacent to each other. Though they or not physically adjacent to each other. To linked list is a chain of elements. And now every node in a linked list has two parts. At least 2 parts. One is the data and other is the link. So linked list can be represented using a PHead, which is the pointer to the head of the list. Of the first element of the list and if you have an empty linked list then the PHead link pointed to a null value and then node element of the linked list can have just one data field. Which is the example given here can have 3 data fields which is the example given here. Where you have name, id gridPts and whatever it has always in the linked list where see up to now it has a single link field or address field and here we see that node is represented to a structure, name, address, and phone and again have a link field. There are many ways in which linked list can be represented in one the look at we look at defining a linked list using 2 structure. One is head structure, one is data node structure. The head structure need not to be represented there are other implementation do not use a separate structure for representing the head node. We are assuming that they are using a separate structure. So you have head structure and data node structure. The head structure will consist of a count of the no. of element in the node and pointed to the first node in the list. The node consists of data and point to the next element of the list. So if you represent this the head structure consist of count is which is an integer and head which is a pointer. In other words in address and

here you have a data which is a data type. Please note this data can have a more than one element it have a structure it can anything and link which is a pointed to the next element. So these are two structures that are used to define type of the element in the linked list as we have represent the linked list. So this is the method in which you represent this. And this is just representation of what seen previously. If you look here, this is typical linked list, which has been created using the structure given here. So here you have the head which pointed to the first node in the list and the count use the no. of element in the list which is 2 and this is a head node. These are data nodes and this consist of the data and the pointed to the next node and this is the data pointed to the next node. This will be null. If the last node in the linked list. This is the representation of the head and count and this is representation, if it is a name. Here the previous one. Put it as the data. If it is the name list. You have the same structure except that. The data will be represented by a character and here you have a person. You can also represented using a person which is the data. Pointed to the data and node which is a represented pointed to the link. Now will have to look at some operations that we have as for as linked list is concern. One is that you have to find out that linked list is empty and another things is because we talking about the linked list. We have to find allocate memory for the node and that is done by this malloc structure. This malloc structure will take the node and will allocate memory location for the data node, when it is created. So the operation we do on linked list implementation of list is same as we do on any list. So you have to create a list. You have add a node, you can delete a node, you can find a node, and can a traverse a list. Please note that in the linked list representation the addition of the node at the beginning, middle or end. It slightly different and similarly deletion beginning, middle or end in the slightly different because we have represented something called a head node. This is a representation of how to create a node. So you will have a pointer and you can create a data here. Have a pointer to the null. It can be represented by a null, which doesn’t have pointed to the next node or you have pointed to the next node. Now please note here that here is creating a two node list. The structure for this. Creating a linked list with two nodes. So first you have defining two nodes. 1st and 2nd in the first node allocating space for the first node you allocating space for the second node and then what you doing is, you are assuming that this is a first node and this is a second node. So you are the second node. The link of the second node is set equal to null. The data of the second node is set equal to 20 and the data of the first node is set equal to 10 and data of the next is made to point to this. How do you get the address of this, this is available here, when you are doing the malloc. So this is a not generalized implementation.

Implementation of hard coding implementation of how to create the two node list. Now please note that when you have a linked list like this, only you can enter the linked list or access the linked list is throw this the pointer or the pointer has to have an address of the first node. Then only you can access the linked list implementation of the list. So now let us look at how to create a list. Please note that we have said that we had separate structure call head, head node, which is consist of the count the no. of element in the node and pointer to the first node of the element. So before you start the count is undefined and head there is no address pointer. Now I want to create a list. So what I do is I put list head equal to null. That is I set this equal null and I set the count to be equal zero. Because this is an empty list. So after the creation operation. This is the output because count is a becoming equal zero and the head set to be null. Please note that, the no. of element in the list at this pointer still zero and you just create the head node. In the other words, the creation operation you just setting of the head node. So this is an implementation of the head node. So you have the data this pnode, is the pointer to the next element. So you put the pointer equal to null and you can also defined something call empty. You what do check whether the list is empty also can be done. Now you want to add an element to an empty list, so before the add operation you already create the empty list. So this is what you will have so this is what you saw in the last slide also. And now you want to add this particular node, data node, into this list. This is the data. This is pNew is nothing but the address of this node. This is an undefined as f node. How do you add this node to this list? So, this what you have seen. So the first step is that you set the link of this to be equal to link of this. It so happen because it is an empty list into which you adding this actually will be set to null. Than you have to change the count of the head node one. Because you will adding one element and the next step you are doing this actually change the link to the pointer to this. So that is the next step, this link, which is the point of the head node of the new node. Which is given by list head equal to this address, which is we know pNew. So what is happen is the link field of the has been set equal to link field of this which is null and the head has been made to point to pNew and this is the state of the list and the count to be one. Because now it contains one node and this what happens of the add operation. So this link, this link been set here. So this is how you added the pNew. Please don’t think of this link. Just pNew give the address of this node. So this is how add 1 to an empty list. Ok. Now we look at adding at the beginning of the list. This is also similar to adding a node at the one node to empty list. That is this is the list before you do adding at the beginning. This is the node data node. That you want to add to the list. When you want to add here. So this is what the status is. Before you do the add operation. Now, what you have do first is the link field of this has to be set equal to the address of this. What you done is. You have set the address of this node to be equal to you have set the link of this node. To be equal to this and the set the ink of this node to be equal to be this. If you reverse the operations here. You want to get the answer. You will what happen trouble because I do not know the address of this well. The address of the available. The address of the available only in this. Initially changed this and put the equal to zero. I have loss the address of this. You cannot do insertion. If you have to initially necessary in this order. First you have what you do set the link of this point to this and then change the head. To point to the first node. So now the list is like this head node 39,75. So this is have add an element to be front of the list. So this is just show you that. When you doing an insertion you are just inserting like this and you not changing to link, while when you are doing insertion of list. Using arrays, we were actually are changing the index of the no. of elements. So suppose you had add an element in an array in the 5th position. And an array consist of 1500 element. Then from the 6th position upto 1500 change the index of all the elements. Linked List 2 Now we are going to see addition of the node in the middle of the list. So, before the add operation. You are assuming that the linked list is like this which consists of a 2 nodes. 39 and 75. PHead is pointing to the first node. Now what we want to do. Yes, we want to add and element 52. Here, that is we want to list look like this now. In order to do that you need to know the address of this node. So that is what is put as previous? So now the node as change after the addition. Now you have 3 nodes. This doesn’t’ change. Now what you are doing is this pNew’s link. Has to be changed are a link has to be fixed at this 75 or the address of 75. How do we that address of 75 nothing but the link of previous. So now you are setting. pNew’s link nothing but P previous link. The address that you set here. The address that you add here. So that is the first step and then this P previous link has to be set equal to this address of pNew. So that the next step. What happen here is first, the pPre link this link is set. Link is equivalent to these step. This step equivalent to this step. That is pNew link is set equal to pPre link. pPre link was actually that address of this node so that is the link and then what you doing? This link now you are changing. You use already the changing this is point to pNew. That is this step. So this link correspond to this step and this link correspond to this step. Please note again. You cannot interchange. If you interchange this you loss this address. That is very important next is add an end of the list. We are not again go to do. But here what happen is. This is node where you want to add. And this is the address of the previous node. But here that the disadvantage of the just not been told here. We assuming that pPre is available.

pPre will not available please note already told you. That can you access the list only from the head nodes. So if you want to find p previous is that you keep on searching the list, till you find a node who is address link field has null. Then you know come to the end of the list and you note that address as P free and then what you do? You set the change the link this point to pNew. And then make p new link is equal to null. But this is one disadvantage of representing list using linked list. Because what happen that if you want to find the end of the list. Assume that this is only 3 nodes found easily. Suppose if you want to insert at end of the node in 1000. Element list representing using a linked list. You have to search from right here and go upto 1000th element. Before and find the address of the 1000 the element. Before you can do this addition. Addition is end of the list is not very convenient or efficient. If you represent the list in this way and other way is you can insert after a particular position. Insert a node with data into the list pointed to after that node. So you are assuming that you know the address of what is trying do is. You want to insert after these you given the address just insert after it is. That is another way of doing is that is what is told here. And this is where you insert. This is what you already seen in the previous test may be insert you first set point this. This is what is initially there. You remove this link. You don’t remove the link, actually. What do you do this? You address know. So set the link do this and make this link into this after inset it. This is already treated. Just the program for that. So up to known you seen creation of empty list, you seen addition to empty list you seen addition to front of the list, you seen addition of the middle of the list and then seen addition after that particular node whose address is given. This is fairly strait forward suppose you had to insert an element in sorted order. Let us 5,10,15,25. And now I want to insert 18 is sorted order. Then again the have to traversal from the beginning. Find out whether the 15 is store the value and then do insertion in middle. So that is also little bit of DTS of as for as insertion to list using a linked list. Now let us look at deletion again deletion you can delete at the first node. Please note this a head node. And this is the list that I have. Now I want to delete the first node that is want to delete 39. Now what I do. I have to make this point to this that all. So what happen is. The head, the link this head now point to this node. And count has to be change to 2. And this location that is the node contain 39, can be recycled or put back into a store of node available for insertion. So this is the deletion. So actually what happen is when you delete to node change a link there is no link to this node. So this in other words are also called as dangling reference. This was deletion of the first node. Now the advantage here was you know the address of the first node. Which is given by this head. But in suppose

you have a general case of deletion. Where you want to delete. Let us say this node, then I need the address of this node if I want to delete the node. Because what happen is have to set this I need address of this to find out and set this link point do this. So, again as we did in the case of Insertion what we doing is we are assuming that we know the address may be conveniently but actually find out the address you have to traversal so, what happen this is Ppre the address of the previous node. So this link may to point to link of this node. Because these link was point it to zero. Then only step for deletion and this is the recycled node. Which is no longer in the picture. So this is for searching. So you can search for a target node. So you can 5,10, 15,20, 95, 100 and if you can search for the less than first node. You can search for greater than last node and you can search for particular node. So if you search less than 5 you won’t find it. If you search greater than 15 you can find it. If you target 15 to 25 own to find it. So you can search like that. So this is again deletion just make it clear. So you have the node and you want to delete. So you want to delete 10. Delete it and put there. So if you want to delete the node other than the node. Deleting the first node. This is a special case. As you told before you can insert or you can access a list we representing linked list using only a node and since this node have now the node has been remove you have to set this node to be 50 are the address of this node. Otherwise you cannot access it. The node that’s only that is has been set to 50 and if you want delete here 50. Set the delete here and this been removed. This is removed of this. So here what you have node is equal to next. Node not next equal. So suppose you want to delete the node after the next so you put node of next is equal to node of next. Which is set to address of next. So that is this step and then free this 50. That is free 10. traverseList. Just you go the through the list pointing to one of the other and till you reach the null. So after this function call pointer value will be null. Because only you after reach a null this end of the list. Some time you want to get the first then the pass position will be point to the first element and otherwise it will point to the next element because of link. So you can other operation like swapping elements. Insert first, last, delete before, last and so on. There are lot of variation you do for insertion, deletion also.

Read More