Introduction to abstract data structures

Dev Zone
1

So I’ve started learning about abstract data structures, are there any helpful hints or tips you guys can give me? - I’m kinda stuck with an academic assignment that I’m working on and it requires you to be able to understand some of the code that a lecturer has written.

We’re working with an implemented queue, and the main functionality of this queue only uses 4 methods, plus a constructor. I actually find it hard to work with because it’s so simple, I can think of ways around it, but it would feel like cheating to me, and my lecturer has also said that we’re not meant to use arrays/arrayLists, etc.

I mean you could just make a load of variables to start with, each variable holding the data that’s passed into the class. Another fact is that in his code, he has only included simple getter and setter methods. Nothing more, nothing less, he has also instructed us to not ‘touch’ his code, just look at it, if we edit it, we could lose marks.

I don’t want to post the code on here, cause I want to be able to work it out myself, I just want a bit of advice on how to get around my problem? It just hasn’t clicked yet, any tips or hints on how I can help myself understand how to get around this assignment.

2

If you're not using an array, are you using linked lists? Is it just the one class?

3

It is just the one class that we're using and I don't think we're actually using linked lists either, well, I don't think we're allowed to yet, at least, I mean my lecturer did say it would be a challenging task, we're trying to make a queue, from the bare-bone mechanics of a linked list. I've been looking up how to do it an everyone seems to either use an array or import a link list, hence why I'm a little confused, I'll double check to see if we're allowed to import a linked list or not.

4

If he doesn't use the LinkedList data structure offered by Java, he probably created his own. It's quite easy to do it. I can post some code, if you want. But I don't want to solve the problem for you.

5

If you're using getter and setter methods for just one class, then it's almost definitely a linked list, in my opinion. Implementing that for yourself should be fairly simple, you just need to figure out how many nodes you'll need and what other extra variables you're using.

And generally, yeah, in data structures classes you will usually be writing code for stacks, linked lists, etc. yourself rather than using pre-existing classes. They say you'll get a better understanding that way. :P

1 Like
6

Please post your implementation just so I can see the difference.... He has given us a minimal link list, but there's only so much you can do with it, I guess that's a part of the challenge though.

7

BTW. A part of the task isn't so much on how to make one, but work on other features, like building the tester for it! :P

8

Do you want a queue that uses generics, or a queue that stores a particular and only that type of data (just int, strings, ...) ?

1 Like
9

Generics would do just fine, that's entirely up to you, and thank you! :)

10

Should be self explainatory: http://nopaste.linux-dev.org/?961210

11

Looking at this, I think it's starting to make more sense to me, I'll have another go at it later on, and I've currently got a mathematical logic lecture, but thank you for the help! :)

12

No problem. :)

13

Okay, so I've got my Queue to work, after thinking about it a bit more, however, I just need to think on how to be able to print out the head, tail and any middle element. any quick/easy ideas?

BTW. Your code was very useful, I understood how yours worked, I just compared it to my lecturer's and yours seemed to make more sense to me. Anyhow, I need to be able to print every element of the link list/queue... Any idea how I could go about doing that?

14

You store two elemets (or pointers): the head of the list and the tail of the list.

To print or output the head, you can see the peek() method I made, it just does: return head.item;

To print the last item, same thing: 

    public Item getTail() {
         if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return tail.item;
    }

To print all the items you can use a while loop like this:

    public void print() {
        while (!isEmpty()) {
            System.out.println(dequeue());
        }
    }

Complete code here: http://nopaste.linux-dev.org/?961384