2

We are just learning about circular queue in class, and I got a few questions. Since we define the tail as the empty space next to the last value, such as shown below: 

|1| |3|4|5|6|

The head will be pointing to the number 3, and the tail will be pointing to the empty space between 1 and 3. I am confused on what happens if that space is filled up, so for example below:

|1|2|3|4|5|6|

Then the head will still be pointing to 3, but the tail needs to be pointing to the next box after the blank box before, thus it will be pointing to 3, or the header. What should I do about this?

Mac
  • 14,615
  • 9
  • 62
  • 80
nonion
  • 826
  • 2
  • 9
  • 18

4 Answers4

6

When this situation occurs, your queue is full. You have a few options when to deal with new items that can be pushed:

  1. discard the pushed event: only when some other item is popped can now items be pushed again. Neither head nor tail is updated.

    Example: Think of an event queue that has filled up, new requests are simple ignored.

  2. discard (pop) the oldest event on the queue: in this case you update both the head and tail pointer one place.

    Example: buffering incomming image frames from a webcam for processing. For a 'live' feed you may prefer to discard the older frames when the processing has a hickup.

  3. create a bigger queue: that is, allocate more memory on the fly

    Example: you use a circular queue since it an efficient implementation that doesn't require memory allocation most of the time when you push items. However, you do not want to loose items on the queue so you allow reallocating more memory once in a while

What the right action is depends on your application.

PS.: Your implementation is based on keeping an empty slot in your queue to distinguish full and empty buffer. Another option is to keep a counter on the number of elements in your queue to make this distinction. More info can be found on Circular buffer (Wikipedia).

catchmeifyoutry
  • 7,179
  • 1
  • 29
  • 26
  • He's asking about a circular queue. – houbysoft Jul 05 '12 at 21:07
  • @houbysoft: Yes, I know. And? – catchmeifyoutry Jul 05 '12 at 21:20
  • A circular queue just doesn't get "full", that's the point of it being circular. – houbysoft Jul 05 '12 at 21:24
  • In other words, only the "discard (pop)" part of your answer is relevant. – houbysoft Jul 05 '12 at 21:24
  • A circular queue is just a datastructure which (by itself) doesn't require dynamic memory reallocation. You can detect when its full, and handle that situation in different ways. Why not always just discard the oldest item? Because its not necessarily what you want, i.e. the reason reasons to implement a queue as a circular queue may be for a different reason than discarding the oldest item. In fact, some implementation throw an Exception when the buffer is full. – catchmeifyoutry Jul 05 '12 at 21:30
  • Well, unless I'm missing something, if you're not always overwriting the last item, you just have a normal, fixed-size queue. – houbysoft Jul 05 '12 at 21:34
  • 1
    Indeed, its an efficient implementation of a fixed size queue. Queues may also be implemented as linked lists (fixed size or not), or naively in an array by inefficiently moving around memory. For what its worth, I think we mostly understand each other, just disagree on what the term 'circular queue' refers to (specific behavior versus specific implementation). – catchmeifyoutry Jul 05 '12 at 21:40
  • For those wondering, CircularFifoQueue, utilizes the feature brought up in point 2 of catchmeifyoutry post, http://stackoverflow.com/a/21699069/1815210 – gimmegimme Feb 15 '17 at 07:30
  • +1 for the PS. This makes sense now "If `Q.head == Q.tail` then the queue underflows, and if `Q.head == Q.tail + 1` then the queue overflows." – razz Oct 13 '18 at 00:42
3

As I thought of it, a circular queue is circular in part because it does not get "filled up". It will simply always hold a set number of elements, throwing out old ones as needed.

So you will never fill up the empty space; if you insert a new element, you'll remove an old element, so there will still be an empty space.

In other words, in your diagram, if you insert a new number, say 0, your a queue that looks like the following (assuming 1 is the last element, 3 the first):

|1| |3|4|5|6|

it will then look as follows:

| |0|3|4|5|6|

However, some implementations of a circular queue simply throw an exception/error when their full length is reached, if that's what you want. Check out for example this.

houbysoft
  • 32,532
  • 24
  • 103
  • 156
  • Thanks for replying, but in this case, if the list is full, when we try to print out all the values, normally it is using a for loop with parameters such as head < tail or tail < head (depending on where they are). for this case, the head = tail, thus this doesn't really work? – nonion Jul 05 '12 at 21:04
  • @NhatLe: It's really just common sense... Start printing at `head`, then do `head++` (and rollover to 0 once you reach the end of the allocated space), etc. Stop when you reach `head == tail`. – houbysoft Jul 05 '12 at 21:09
  • @nhatle: and why would `head == tail` in "this case"? Head will be at `0`, tail at the empty space. – houbysoft Jul 05 '12 at 21:10
  • @houbysoft By the way, the implementation that you link to doesn't just discard the oldest element, but shows an error message. The author calls it a "queue overflow" state (thus the queue can indeed fill up). – catchmeifyoutry Jul 05 '12 at 21:56
  • 1
    @catchmeifyoutry: hah, you are correct. Fair enough then, it seems that people think of a "circular queue" more in the sense in which you are thinking about it... Gave you a +1. – houbysoft Jul 05 '12 at 22:06
  • Cheers! Well, I think we both learned that circular queue means different things to different people :). Nice exchanging thoughts with you. – catchmeifyoutry Jul 05 '12 at 22:25
0

Here is the most succinct explanation about queues that I have ever found. You can expand on your queues based on this foundation. Source: "Algorithms," by Robert Sedgewick.

const max=100;

var queue: aray[0..max]of integer;
     head,tail: integer;

procedure put(v:integer);    
  begin
    queue[tail] := v;   
    tail := tail + 1;   
    if (tail > max) then tail := 0;
  end;

function get: integer;  
  begin
    get := queue[head];
    head := head + 1;   
    if (head > max) then head := 0; 
  end;

procedure queueinitialize;   
  begin
    head := 0;
    tail := 0;
  end;

function queueempty: boolean;   
  begin   
    queueempty := (head = tail);
  end;

"It is necessary to maintain two indices, one to the beginning of the queue (head) and one to the end (tail). The contents of the queue are all the elements in the array between head and tail, taking into account the "wraparound" back to 0 when the end of the array is encountered. If head = tail then the queue is defined to be empty; if head = tail + 1, or tail = max and head = 0, it is defined to be full."

Mike Jablonski
  • 1,703
  • 6
  • 27
  • 41
0

When the head and tail points to the same place then we say that the queue is full.No more elements can be added.To add any element ,you will have to remove an element from the queue.With this the head will get incremented and a space is again generated.

Satyapriya Krishna
  • 73
  • 7