Queue - Data Structures & Algorithms Tutorials In Python #8

Key Takeaways

we are going to discuss queue data structure in this tutorial and here is the list of topics along with their time line so if you want to skip ahead feel free you might have used portals such as yahoo finance or money control.com or to track down the stock prices now the way these portals get stock prices is from stock exchanges such as New York Stock Exchange and if you look at the technical architecture the engineering things team sitting at New York Stock Exchange will be supplying the prices let's say these are the prices for a walmart stock at 11 o'clock one minute the price was 131 and then at 2 minute the price was 132 point well they supply these prices continuously to portal like Yahoo Finance and they will display various charts and information now going deeper into technical architecture one way to solve this problem would be the engineering team at Yahoo Finance will develop an HTTP server which can accept the HTTP POST request coming in from New York Stock Exchange so the engineering team sitting here in NY SC would make HTTP POST calls along with these JSON objects this could be one architecture and it will work this way you can supply the stock prices to the other end but there are a couple of issues with this architecture the first problem is what if the HTTP server is done in that case these guys will be making the calls and it will result in two loss of messages so the prices during the time frame that the HTTP server was down would be lost so all these prices will be lost and for Yahoo Finance let's say after five minute the server comes back up there is no way to retrieve those old prices because they made this synchronous calls which Yahoo Finance guys couldn't process because that server was down and now you lost all that information other issue is tomorrow if Google Finance wants to receive the same pricing feed now the engineering team at & ysc will have to change their code and use Google's URL to supply them the prices this is called tightly coupled architecture and it has lot of issues such as every time you want to on board a new consumer you have to make code changes and if the system is tightly coupled let's say if there is any change on the consumer side then producer side will also have to change and it's a nasty infrastructure there are just a lot of issues what if you had a memory buffer like this where NYSC can just put the prices one by one so at 11 o'clock one minute they put this price at 2 minute they put this price and they just keep on pushing this prices and on the other hand side Yahoo Finance or Google Finance guys can receive these prices in the order that they were pushed in now there are ways where once Yahoo Finance consumes this particular price you know their pointer will move here so that Google Finance can still consume this it's not like once Yahoo Finance consumed this price Google Finance cannot consume it they will have a different pointer so that will work out so don't worry about that but this data structure that we used here is called Q and Q allows you to establish loose coupling so when there is a loose coupling between these system tomorrow less safe money control.com bonds to use this prices & ysc doesn't have to make any change actually they can just keep on pushing the prices to the same memory buffer and money control can just consume it so it's a very flexible infrastructure with minimum amount of issue this problem is also called producer consumer problem where one entities produce doing some information and one other entity is consuming the information produced by a producer in a way that they are not tightly coupled here whatever is pushed first in the buffer is consumed first hence it is called FIFO or first in first out data structure if you remember from our last stack data structure it was last in first out versus you is first in first out and you have already noticed you in real life let's say if you are at a movie theater buying tickets whoever is standing first will get the first turn so it's like first in first out these are the code snippets in different programming languages for cue along with the cue classes for example Java uses linked lists as a cue implementation so this is not a typo it actually uses linked lists as an implementation for Q so Q is an interface which is implemented by linked list data structure here you see like you are adding Phi and 89 and when you say remove or you will get Phi back similarly in Python you can use one of these three approaches to implement Q now we will see how to use Q in Python you can use lists as a queue in Python here I have created a list called Walmart stock price queue and whenever you want to insert an element in the queue you can use this insert operation you are always inserting at the 0th position okay so the first price that you had was this and the second price you had was this let's say and let me insert one more price call 1:35 every time when I insert an element at 0th position remaining elements gets pushed forward okay when you do this and when I look at my queue right now so the queue will look like this so you see you inserted 131 first so 131 is here then hundred 3235 now when you do pop Q is first in first out data structure stack is last in first out so when I do pop I just tell me what do you expect to get out of this pop operation it is first in first out so the first thing that was in was 131 point 1 0 when you do pop see you got that thing back when you do popper King you will get 130 2.12 pop again you've got the last 11 135 now my queue is empty so when I do pop again imagine what's gonna happen yes it's gonna throw an exception while list can work okay as a queue it has problems associated with dynamic array in our past tutorials we have seen what kind of issues you might face when you are using dynamic array such as when you are allocating new elements and if it exists the capacity it will have to allocate new memory area and then it will have to copy all those elements okay so using lists is not very much recommended as a queue you can use other approach which is using DQ from collections module now in last tutorial we used DQ as a stack so DQ is double-ended queue it's very flexible it can be used as a stack as well as a queue so here I have created a variable called queue which is an instance of DQ and let's see how we can use it as our queue data structure so so this has a function called append left this is the documentation of DQ if it was tagged we would have used a pen we already did that in our last tutorial on stack but in queue you're always appending at the left hand side so I'll append bunch of values okay so let me a pan whatever some random values and then when I do Q dot pop tell me what we expect Q is first in first out data structure so whoever got first in you know five that comes out first very obvious like if you're standing in a queue to buy a ticket for your train whoever got into queue first will get his ticket first right it's just a simple principle of queue that we use in our day-to-day life and now you then you do Q dot pop and you get 27 back you do Q dot pop one more time and it will throw you an exception so now let's implement proper queue class in Python using collection dot DQ and just to save some time I'm gonna just copy paste the whole class because the class implementation is pretty simple Here I am creating a class where there is a class object called buffer which is an instance of DQ Q will typically have n q + DQ method and Q is placing an element in the queue it's like you are standing in the queue to buy your movie ticket and DQ means you bought a ticket so now you are out of the queue and these are helper methods whether the queue is empty or not oh and what is the size so if you look at this class pretty straight for a very very simple class okay and we can use now our Walmart Stock Exchange price example to put a couple of elements so here I created a queue using this queue object and then I have inserted couple of dictionary elements which represents a Walmart stock price okay so I have a typo I'm going to remove that and these are the stock prices so at 11 o'clock one eleven o'clock two-minute three-minute different prices and I use NQ to put all those elements in the queue when I print P Q dot buffer it will show me all these elements okay one by one and when I do PQ dot DQ so just think about this as your Yahoo Finance course so the engineering team on the Yahoo Finance side they will use DQ whereas on your stock exchange side they will NQ all the prices okay so at Yahoo Finance when I say DQ DQ you eue again a typo I will get the first prize at 11 o'clock and one minute when I run this same code again see Iliana o'clock and two same code again 11 o'clock 3 so this way I can keep on accessing these elements one by one I just quickly show you the size method so I retain this again and if you do PQ dot size it pins the size as 3 so that's all I had for coding part there is a website called Big O cheat sheet comm which will show you the Big O complexities for different data structures so here in the queue data structure average access and search complexity is order of n whereas insertion and deletion is order of 1 and these are the worst case complexity so you can refer to that I am going to create more tutorials where I will be comparing different data structures for different type of problems and we'll be doing in depth Big O analysis at that point now moving to the most interesting part of this tutorial which is an exercise yes I have an exercise for you all and let me open that this github MD page I am going to provide a link of this in video description so you can refer to the exercise we have to exercise for this tutorial you can just read through the description I have provided some important links here so let me repeat the same thing again and again I know I'm becoming very boring just by watching the tutorial you are not going to learn any coding it is a waste of your time you can learn coding only by practicing it and these exercises are the best way to practice whatever you have learnt in my video so go ahead practice it on your own first and once you have given it a try you can click on the solution link and refer to the solution that I have provided but do not click on the solution directly otherwise it will inject kovat 19 virus on your computer and your virus will get 105 degree fever ok so if you want to save your laptop your computer try it on your own first and then look at the solution alright thank you very much for watching bye