[insidious]

There are a few ways queus can be implemented. Just like any other data structure, there is no 'right' implementation. It all depends on the system you're running on.

As a basic overview:
A queue is a FIFO data structure. Just like any Queue in real life (think of standing in line for Mcdonalds or something) the person in the front has to/is served first.

Now i'm not sure what language you're currently learning, so I'll do some sample code in C, since that's what i'm currently working with and most comfortable with.

A very simple static implementation of a queue (with an array) might look something like this:

Code:

#include <stdio.h>
#include <stdlib.h>

int N = 10;
int top = 0;  // pointing to the top element of the queue
int count = 0; // number of element in the queue;
int array[N];  // array to store elements
void enqueue(int element) {
  if (count < N) {
     int last = (top + count) % N;
     array[last] = element;
     count = count + 1;
     return;
  }
  else {
     printf("Queue is Full"); //screw actual error stuff in an example
  }
}

int dequeue() {
  if (count > 0) {
     int result = array[top];
     top = (top + 1) % N;
     count = count -1;
     return result;
  }
  else {
     printf("Queue is Empty);
  }
}
int main(){
   enqueue(3);
   enqueue(8);
   dequeue();
   dequeue();
}

The "Queue" functions in this static implementation is handled by the math in enqueue and dequeue along with the global variables keeping track of which element should be 'dequeued' and which element should be put into the queue.

I recommend putting this code into an IDE or just into a text editor, compiling, and debugging with GDB (or IDE's Debugger) if you are familiar with C in order to figure out exactly what it is doing. I find debugging a pretty good 'real-world-way' to learn data structures like Queues. It's good to do with simple snippets like this, because you can really see whats going on.

If you're not familiar with C, the syntax is quite similiar to Java/easy to understand I think, so it would be easy enough to translate it. This code doesn't use any pointers or anything that's not in Java or more protected languages.

It can hold at most 10 elements, unless you change N. that's why it's static, the queue cannot be changed. This might be a good implementation if you're working with low-memory hardware, maybe it's some type of embedded ARM devices, or something. There's a use case for everything out there.


For a more complex implementation, you can look at this guys queue implementation with a LinkedList: https://gist.github.com/mycodeschool/7510222



There's really no 'right or wrong' way to implement a datastructure. There is defintely a best way for a specific system/architecture/purpose, however. There are simply high-level rules that describe what a datastructure should do and how it should behave. As long as you're code does what is described, then BANG you got the datastructure. It's really that simple.

Code:

Purpose of a Queue:

Well, whenever you have something that is best services in a FIFO manner, you can use a Queue. Maybe a website is getting millions of requests a second but you can only service, like, 1,000 at once. The fairest thing to do would be to service the requests which came in first, first. So, you would start servicing requests, and then if more requests come in that you can't handle you stuff those requests into a Queue.

so maybe it would look something like this:

Code:

CURRENTLY HANDLING                      INCOMING REQUESTS
1000 REQUESTS                                 999,000

QUEUE
INCOMING REQUESTS
...
1,000
1,000
1,000
1,000
NEXT to be serviced (below):
1,000          <-----First element to be dequeue()'d

Again, it's just like standing in line for McDonalds.

(we're in the java board)
But yeah I get it now. Kind of like a stack with an open bottom? Seems simplistic enough.

Yeah, pretty much. It's important to think of it as it's own data structure obviously, but yeah pretty much a stack with an open bottom, where the first element in is the first element out.