Anonymous user
Queue/Definition: Difference between revisions
→{{header|C}}: added two implementations
No edit summary |
(→{{header|C}}: added two implementations) |
||
Line 399:
=={{header|C}}==
===Dynamic array===
<lang c>#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
int *buf;
size_t head, tail, alloc;
} queue_t, *queue;
queue q_new()
{
queue q = malloc(sizeof(queue_t));
q->buf = malloc(sizeof(int) * (q->alloc = 16));
q->head = q->tail;
return q;
}
inline int q_compact(queue q)
{
if (q->head * 2 >= q->alloc) {
memcpy(q->buf, q->buf + q->head,
sizeof(int) * (q->tail - q->head));
q->tail -= q->head;
q->head = 0;
return 1;
}
return q->tail * 2 < q->alloc;
}
int empty(queue q)
{
return q->tail == q->head;
}
void enqueue(queue q, int n)
{
if (q->tail >= q->alloc && !q_compact(q)) {
q->alloc *= 2;
q->buf = realloc(q->buf, sizeof(int) * q->alloc);
}
q->buf[q->tail++] = n;
return;
}
int dequeue(queue q, int *n)
{
if (q->tail - q->head < 1) return 0;
*n = q->buf[--q->tail];
if (q->alloc >= 512 && q_compact(q)) {
q->alloc /= 2;
q->buf = realloc(q->buf, sizeof(int) * q->alloc);
}
return 1;
}</lang>
===Doubly linked list===
<lang c>#include <stdio.h>
#include <stdlib.h>
typedef struct node_t node_t, *node, *queue;
struct node_t { int val; node prev, next; };
#define HEAD(q) q->prev
#define TAIL(q) q->next
queue q_new()
{
node q = malloc(sizeof(node_t));
q->next = q->prev = 0;
return q;
}
int empty(queue q)
{
return !HEAD(q);
}
void enqueue(queue q, int n)
{
node nd = malloc(sizeof(node_t));
nd->val = n;
if (!HEAD(q)) HEAD(q) = nd;
nd->prev = TAIL(q);
if (nd->prev) nd->prev->next = nd;
TAIL(q) = nd;
nd->next = 0;
}
int dequeue(queue q, int *val)
{
node tmp = HEAD(q);
if (!tmp) return 0;
*val = tmp->val;
HEAD(q) = tmp->next;
if (TAIL(q) == tmp) TAIL(q) = 0;
free(tmp);
return 1;
}
</lang>
'''Text code'''
This main function works with both implementions above.
<lang c>int main()
{
int i, n;
queue q = q_new();
for (i = 0; i < 100000000; i++) {
n = rand();
if (n > RAND_MAX / 2) {
// printf("+ %d\n", n);
enqueue(q, n);
} else {
if (!dequeue(q, &n)) {
// printf("empty\n");
continue;
}
// printf("- %d\n", n);
}
}
while (dequeue(q, &n));// printf("- %d\n", n);
return 0;
}</lang>
Of the above two programs, for int types the array method is about twice as fast for the test code given. The doubly linked list is marginally faster than the <code>sys/queue.h</code> below.
===sys/queue.h===
Using the <tt>sys/queue.h</tt>, which is not POSIX.1-2001 (but it is BSD). The example allows to push/pop int values, but instead of <tt>int</tt> one can use <tt>void *</tt> and push/pop any kind of "object" (of course changes to the commodity functions <tt>m_queue</tt> and <tt>m_dequeue</tt> are needed)
| |||