Week of January 22nd, 2014: Queues, stacks, linked lists and general OOP

This week was fantastic. I was extremely fascinated in the runtime difference between queues and stacks during lab 2, as I have always been interested in finding the most efficient ways to compile/group/sort/extract information. The last section of the lab really stumped my partner and me, as we thought that queues took longer to work through due to python having to go through all the entries starting form the back; hence, as the amount of items in the queue grows it takes longer and longer to get to the front, whereas the stack run times seem to be about the same at every run. We tried to implement a "reverse" queue that would keep the front item of the first queue as its back item so as to provide quicker access for the dequeue function (so in effect, we ignore everything in the queue that wasn't the first or last item.) However, our TA told us that the run time wasn't increasing due to the amount of items growing, but rather because every time we dequeue an item, we have to "shift" the whole queue down. He suggested we look into linked lists, which provide adjacent references and thus allow the first and the last to be extracted quicker.

This is something that I really want to investigate further (even on my own time) as I'm now interested in when it would  be more advantageous to implement a queue vs a stack vs now a linked list. For example, if you need to extract something from the middle of the linked list, it takes even longer, so it isn't a ubiquitous solution.

I want to be super attentive to whenever we can implement either structure so that for myself I understand what the quickest way to get information is in any context. For the purposes of lab 2 I think the linked list would've been perfect, but I still would want to look into the reverse queue idea some time in the future. Even if it fails I'll still understand queues better.

Overall, a great week as I was also more comfortable using __init__ and defining classes (which I completely didn't understand last week). While I've done a lot of programming in the past, this is my first exposure to OOP so I am still learning the ropes. I don't have any problem running loop structures or understanding control flow/algorithms but the syntax has been difficult. Next lab I will try to be the driver specifically for the roles where classes are initialized and defined so I can get more practice !