(11-28-2016, 04:54 AM)insidious Wrote: 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.

(11-28-2016, 04:33 PM)DarkMuse Wrote:

(11-28-2016, 04:54 AM)insidious Wrote: 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.

(11-29-2016, 08:05 AM)bitm0de Wrote: Queue is a stack but FIFO rather than LIFO.

(11-29-2016, 09:45 PM)insidious Wrote:

(11-29-2016, 08:05 AM)bitm0de Wrote: Queue is a stack but FIFO rather than LIFO.

It's grossly incorrect to call a queue a stack. It is FIFO rather than LIFO but they are fundamentally different structures.

(11-29-2016, 09:45 PM)insidious Wrote:

(11-29-2016, 08:05 AM)bitm0de Wrote: Queue is a stack but FIFO rather than LIFO.

It's grossly incorrect to call a queue a stack. It is FIFO rather than LIFO but they are fundamentally different structures.

(11-29-2016, 09:50 PM)bitm0de Wrote:

(11-29-2016, 09:45 PM)insidious Wrote:

(11-29-2016, 08:05 AM)bitm0de Wrote: Queue is a stack but FIFO rather than LIFO.

It's grossly incorrect to call a queue a stack. It is FIFO rather than LIFO but they are fundamentally different structures.

I think you only read the first 4 words of my post so you could attempt to correct me by saying exactly what I've already said in the last part of my previous post about FIFO vs LIFO.

He didn't understand what a queue was therefore relating it to the stack and explaining the difference between the two should've been fine for an explanation that leads to his understanding IMO. And the fact that implementation in comparison can be almost 90% similar except for how the dequeue process works makes it an acceptable comparison too. There IS a reason why they were given similar acronyms.

You're saying I can't use similes or metaphors to help someone learn? Now you're just being a pessimist. :/ That's like saying the antonym of some word can't be used to explain the meaning of the opposite word.

Quote:And the fact that implementation in comparison can be almost 90% similar except for how the dequeue process works makes it an acceptable comparison too. There IS a reason why they were given similar acronyms.

Quote:I think you only read the first 4 words of my post so you could attempt to correct me by saying exactly what I've already said in the last part of my previous post about FIFO vs LIFO.

(11-29-2016, 10:10 PM)insidious Wrote:

(11-29-2016, 09:50 PM)bitm0de Wrote:

(11-29-2016, 09:45 PM)insidious Wrote: It's grossly incorrect to call a queue a stack. It is FIFO rather than LIFO but they are fundamentally different structures.

I think you only read the first 4 words of my post so you could attempt to correct me by saying exactly what I've already said in the last part of my previous post about FIFO vs LIFO.

He didn't understand what a queue was therefore relating it to the stack and explaining the difference between the two should've been fine for an explanation that leads to his understanding IMO. And the fact that implementation in comparison can be almost 90% similar except for how the dequeue process works makes it an acceptable comparison too. There IS a reason why they were given similar acronyms.

You're saying I can't use similes or metaphors to help someone learn? Now you're just being a pessimist. :/ That's like saying the antonym of some word can't be used to explain the meaning of the opposite word.

Simile:
a figure of speech involving the comparison of one thing with another thing of a different kind, used to make a description more emphatic or vivid (e.g., as brave as a lion, crazy like a fox ).
"A Queue is a stack" does not qualify as simile. When you say something IS something else, that does not mean it is like something else.

Metaphor:
a figure of speech in which a word or phrase is applied to an object or action to which it is not literally applicable.
"“I had fallen through a trapdoor of depression,” said Mark, who was fond of theatrical metaphors"

Yeee doesn't work.


Listen, i'm not trying to kill your vibe here (maybe a bit), but I don't think it's right to even leave the possibility of leading people in the wrong direction. It can lead to complications down the line.

Quote:And the fact that implementation in comparison can be almost 90% similar except for how the dequeue process works makes it an acceptable comparison too. There IS a reason why they were given similar acronyms.

I didn't say it was an unnaceptable comparison. If you had read my previous posts, I did compare them, and even admit their similarity.
Sure, Queue's and Stacks are very similar. They are, I never denied that. But they are not each other.


Sure, implementation is the same. But that's like saying insertion sort is selection sort because the concept is fundamentally the same. But they aren't, their implementation is totally different and so are their use cases.

Quote:I think you only read the first 4 words of my post so you could attempt to correct me by saying exactly what I've already said in the last part of my previous post about FIFO vs LIFO.

tsk tsk, why would you assume that? I hope you are not taking this personally, and I certainly do not mean it that way. We're talking about abstract concepts here not what we think the other person read in order to shoot shade at the other.

It looks like you know your data structures; good, cool, I'm happy you commented in this thread to help other people out. I'm just trying to provide the clearest possible explanation.

On a test, if @"TotallyRandUser128372139" was asked: "What is a Queue?" and they put: A Queue is a Stack, but FIFO instead of LIFO, they would only get half points. Because a Queue isn't a stack. The correct phrasing would be A Queue is LIKE a stack, but FIFO instead of LIFO that is a perfectly well written simile and absolutely acceptable.


TL;DR I'm being a grammar Nazi but hopefully you glean something from this

[video=youtube]http://https://youtu.be/2E0RfaUyQvE[/video]