I am taking a Data Structures using Java course, and we covered implementing stacks using arrays and using Linked Lists. For the homework we are asked to develop a stack using what is refered to as physical implementation three, that looks like a linked list but the data element of the linked list refers to an array. Is there a name for this type of stack implementation, I have been trying to write the code for this structure but cannot seem to wrap my brain around it. The professor made it seem like this type of implementation was commonly used.
I think what you're describing would look like this in Java: each LinkedList element would hold an Integer. That intValue() of that Integer would be an index into an array. This would be a good implementation in a language, like, say, FORTRAN 77, where there is no dynamic memory, and no real pointers, so all the data that might be in the stack is allocated as part of a big array. In Java, it makes no sense at all; since everything (non-primitive, anyway) is a pointer in Java, the extra level of indirection buys you nothing, just adds complexity. Before implementing this, though, you should make sure you understand what's actually being asked for, because my guess as to what you're describing may be wrong. Ask the instructor or T.A. for clarification if you need it; you're paying for the education, after all.
Man, if students talked to their instructors, we wouldn't have half the traffic we have in the saloon. Looking back into the dusty recesses of my mind, I seem to remember the array implementation of a linked list or stack from my Data Structures class. The problem statement is that you don't have dynamic memory allocation in your operating system but you still want a dynamic data structure, like a stack or linked list. So what you do is statically allocate a chunk of memory as an array and wrap it with stack or list methods (i.e. pop(), push() or add(), remove()). It is left up as an exercise for the student to figure out how to maintain order within the stack, what to do when there's no more room in the structure and so on. I'm sure somewhere I have my source code in a mainframe version of Pascal!
Well, I did a linked list in an array once in COBOL. Each array entry included the index of the "next" in some logical order. But a stack should always just be in order. Or do you have to support operations like swap the first two entries that would move them out of order? I guess you could fudge the pointers instead of popping two and pushing them back in other order.
A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
You have the right idea, Stan. The "order" of the stack isn't enforced by the array, it's enforced by the data structure and the methods used to manipulate it. It's an example of how an API can be used to abstract the inner workings of something, making it look and function like something much different. I'd say more, but you know, someone is working on their homework. . .