Implement a Stack - Java Interview Coding Challenge #4 [Java Brains]

in this video we're gonna tackle an interview question which is a data structure based I hope you guys are familiar that stats the interview question is implement a stack in Java so if somebody asks you this question in an interview the first thing you should think about is what are the pieces of information that you need in order to implement a stack in Java you don't want to be implementing the whole thing so you need to ask what is it that they want for example what are the api's it's it's generally good practice to think about okay do I have all the information to answer a question in any interview in this particular thing the first question that you would ask is what does that stack do like what are the API is that you need to provide for the stack Java comes with a stack which has its API so that would be a good starting point for you to say okay do you want me to implement these api's so it would be the first question so what are the pairs that the stack provides before that what does the stack even do a stack is a last in first out either structure or the first and last out data structure kind of like stack of plates really so you have a stack of plates you put a plate down and then you put another plate and then another plate down so when you need to take all the plate the plate that was put in last is what gets out first and then the plate that was put in first is all the way at the bottom and that's what comes out last so you want to be able to use a stack to perform this operation gonna be able to put things into the stack and then remove things from the stack but you don't get control over which particular item you want to remove there's gonna be one foot and one remove function when you remove something to think that gets removed is the last thing that you put in similar to have the stack of plates performs so that's the lastin first-out structure so the stack API in Java has methods for it so there is push and there's pop push there's a way for you to take in an argument and pass that argument to the push method and say push this particular thing it's gonna push that on the top of the stack pop is something that does not take any arguments but then it returns an item it returns the item that was last pushed then picks the item from the top of the stack so if you let's say you push one push two and push three and then pop you get three another pop you get two in another part you get one right first in last out it is another API the stack provides in Java which is something called big peak is something that does not modify the state of the stack it just returns the reference to the topmost item in the sack without removing it when you do a pop you get the item that was at the top of the stack when you do a peak you don't remove the item from the top of the stack but incidentally you just get a reference to it but it's still on the top of the stack so you can do a peak you get an item the next time you do a pop you're gonna get the same item but then the stack is modified and the item is no longer in the stack whereas with the Pete leave the stack as is alright alright so let's try writing some pseudocode implement those methods before we get into the pseudocode you need to think about what's the data structure that you're going to be using to keep those elements in your class so you're gonna be creating a stack class when you need some data structure for it the simplest data structure you can use for this is an array so you can put things into an array and remove things from an array an array is index based right give it an index you can get the element which is at that end deck so since we're using an array for a stack we have to make it a little more restrictive and what gets remote and what gets added so let's write some pseudocode to see that in action alright so what we have here is a stack class which is going to have an array off maybe size and we can define I'm thinking maybe we can define a capacity for for the area there's a good question to ask back at interior do you want stacks to be initialized with a certain capacity that's the case then you can take the capacity as a constructor or hard and then create an array with that capacity and there's what you're gonna be using to keep track off the stack this also lets you implement is stack full method so you can check if the stack is equal to the capacity then you can prevent for the pushes from happening and throw out an error message or throw an error for example so this is what we need and then of course we need like like a pointer all right so let's say whatever is the top talk with a sec I'm gonna call this the top and this is going to point to this top of the step so let's yeah and marry like this right so the top of the stack is in July is that - one position there you go now then you push something to the stack let's say there's a stack you push something it goes to the bottom push something else goes over here push something else goes over here and then when you pop three goes out then two goes out then one goes out so in this case we're using the array for this if first time you push one it's gonna sit here and the top is gonna move over here next time when you push two it's gonna go here top is gonna go here three top is gonna go here and then you do a pop you're gonna take the item out we're done this and then of course before you return you move top to this point so that the next time there is a pop you return to and so on so it's a very simple translation from array methods to the stack methods where you're kind of making things a little more restrictive in the sense of where the element gets removed from and where elements gets added into the array all right so let's let's look at the code in which we can implement this there are a few conditions where you need to be careful about how you need to handle it and again these are good questions to ask the interviewer we will tackle that when we get there but let's look at our simple code implementation for this so we have this class called stack have provided a class here which is going to contain by integer array of course this is another question before you come to this assumption you should ask the interviewer what is the data structure of the elements inside the stack if they want it to be any arbitrary object then things are going to be a little different the one that if you they want you to use generics then this needs to be a generic class for the sake of simplicity in this example I'm assuming that all the elements of the stack are integers this could be something that the interviewer would be okay with because they want to test your skills and data structures and how you can come up with push and pop logic they may not be that worried about and handling genetics and all that stuff but then it depends on the interview this case integers so I'm creating an integer array and then I'm creating this top pointer which is going to point to the top of the stack where it is in the and then I have a capacity in teacher which is what I'm going to use to initialize the Orion I'm also gonna hold on to the capacity so that we can detect situations where the stack is full all right now I'm going to create a constructor which takes in this capacity because there's gonna let me initialize the stack with a certain amount of spaces and I'm going to create this array inside the constructor so I'm going to create a new integer array of that size capacity and then I'm going to save the capacity value as member variable for class and then I'm going to initialize stop as minus 1 because you haven't even hit the zeroth element yet top is going to get to the zeroth element when the first element is pushed into the array now the 3 ApS that we need to implement we need to implement the push which takes in an item which is an integer and then it returns a white right it doesn't return anything it just pushes the item to the stack the next API is the pop which doesn't take any arguments but then in turn it turns an integer which is the item at the top of the stack and then the third API that we can implement is the peak which doesn't take in an argument but it returns the top of the stack so the difference between the pop and the peak is that the pop modifies the stack and removes the top element from the stack the peak does not modify the stack it leaves the top element that it just returns the value of it all right so let's implement this what do you need to do to push an item on the sack well that's simple increment the top and then array off top equals the item which is what I'm doing here sorry off to us per stop equals items it's a pre increment top gets incremented and the item gets saved into the area hit that incremented position all right how about pop you get the item out and then you determine table you can guess what that looks like you're done or if top - - this is a post Dickerman so I'm going to use that value of top to get the item from the array and then I'm going to do a - - for that the value of top gets decremented by 1 all right peak is just going to return array off top so it doesn't modify the stack in the sense that it doesn't modify the pointer where top is pointing to it just gets the item from the array so some of you might be wondering well I am decrementing table but I'm not clearing out the element in there right I'm just moving the pointer but the item is still there in the array is that a problem well it's not a problem because if the top has moved the next time you do a pop it is gonna look at the value in the top is pointing to next time we do a push it overwrites the existing value so you don't necessarily have to clear out the element from the array let it be there next time you push it will overwrite the position there if you never push the top is never gonna go there and it's always gonna learn refer to the items below it so it should be fine you don't have to override it oh the second question that you might be wondering is how do you handle inner conditions now what if I pop an item on an empty stack what if I push an item and the stack has already reached the capacity and you cannot go any more this would be a question what do you want there are conditions to be you're gathering requirements about the program that you're trying to write so do you say you can ask the interviewer do you want me to throw an exception or do you want me to just quit the program it's very unlikely that you would quit the program for something like this it's typically like you throw a runtime exception so let's say the interviewer says just throw a runtime exception so in that case you can check before you do a push if the capacity has been met if the capacity has already been met then you don't want to push through a new runtime exception how would you check if the stack is full you have a top pointer and you know what the capacity is you remember we are storing the capacity this is gonna be handy in that case you can check if the top is equal to the capacity if it is then the stack is full then you throw an exception how do you know if the stack is empty well you check if top is equal to minus 1 if the value is minus 1 then the stack is empty so one thing that you could do is create utility methods like is stack full is full or as MD which does this so that you don't have to repeat these checks every time so you can tell the interviewer I'm gonna provide these as API so that I can use that in my code and maybe the consumer of your stack class can also check if the stack is empty or full so I can say this full as one method is empty is another method and I can use that to check the bound conditions right so if full if is full then throw a new runtime exception status for similarly if is empty throw your runtime exception stack is empty similarly you do that for the peak if it's empty throw that runtime exception now how would the is felonies empty methods look like very simple is empty is gonna check if the top is equal to minus one this full is gonna check if top is equal to capacity minus one because you remember we started out stack with minus one and when the first element is added top is equal to zero so you need to decrement one from the capacity to check if to check if the stack is actually full you know implement stacks using other data structures like linked lists for example but again make sure to ask the interviewer what data structure they want you to implement this n this was the array way of lamenting stacks in Java

Channel: Java Brains

Views: 45,435

Rating: 4.9202394 out of 5

Keywords: java brains, java, interview, coding, coding challenge, java interview, java interview questions, interview coding challenge, interview practice, koushik, koushik kothagal, java interview videos, java interview challenge videos, brains, kothagal, kaushik, tutorial, programming, eclipse, beginner, challenge, java programming, java tutorial for beginners, training, stack, stack in java, java stack, implement a stack

Id: X7asXkoYWCQ

Length: 11min 41sec (701 seconds)

Published: Mon Aug 05 2019