There is a question that I have been trying to solve for a while but I'm having difficulty to grasp the correct implementation for it. If we write a program that will manipulate thousands of records, each comprising product name, type, serial number, retail price, etc. In each case below, explain which Abstract Data Type (Queue, Stack, Unsorted and Sorted List) you would use, and which implementation (array or linked structure). Briefly justify your choices.
1) Records will be retrieved in the same order they were stored. There is no telling in advance how many records will be processed and how.
2) All records will be inserted at the beginning, once and in no particular order. They will be retrieved very frequently, based on serial number.
3) A large but unknown number of product records will be inserted, as and when needed. They will seldom be retrieved individually. Most operations will consist of processing all records at one go e.g., printing all.
What do you guys think?
Think of what each data structure is intended to do and the access patterns provided in the question and the answers for one and two become self-evident. Three is a bit trickier, but the information you do have is that you have no information about how this data will be used other than the high likelihood that all of it will be used.
Queue is a pipe. Stuff goes in one side and comes out the other in the same order (First in, first out, AKA FIFO). You may or may not be able to see anything in the queue other than the item about to come out. In other words, in order to so much as look at the next item in the queue you have to remove the current item. Searching is a very bad idea because likely you can't search it short of taking everything out and putting it all back in again.
Stack is just that. A pile of stuff. You put stuff on top of the pile, then you take stuff of the pile. Things come out of the stack in the reverse order to which they were put in. This is first in, last out or FILO. Again, you may not be able to see anything but the top-most item in the stack, so to get at the next item down you have to remove the top item. Searching is a bad idea for the same reason as the queue.
Anything could be put anywhere. Putting stuff into the list is a cakewalk because you don't care where it goes. Finding stuff in the list... That's a bummer. You literally have to look at each item one by one (linear search) until you find what you're looking for. If youy don't care what is in the list and never have to search it, this is your data structure. At least until you gather and usage statistics and find some optimizations.
Everything is in its place according to some specified schema. This makes finding stuff stupidly easy. It's possible that you can go straight to the sought item, and if not you can generally subdivide the list over and over because if the item wasn't on one side of wherever you choose look it must be on the other side (binary search). Finding is easy, but whatever you insert has to be carefully placed and this can be quite expensive. But if you build the list once and then repeatedly search it, you almost always come out ahead.