Tail Queue in sys/queue.h

sys/queue.h移植自FreeBSD,在一般版本Linux都有。它基本实现以下几种功能

1. queue: 将元素插入到尾部，从头部删除元素。
2. list:可以对它正序、逆序遍历。对这个队列进行插入/删除操作。
3. 因为功能1和功能2，可以吧Tail Queue当做stack用。
4. 可以实现类似STL中的deque功能。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/queue.h>

struct Node
{
  char c;
  TAILQ_ENTRY(Node) nodes;
};

TAILQ_HEAD(head_s, Node) head;//head_s是这个帮助生成的struct名字，可以不填

void buildQueue()
{
  TAILQ_INIT(&head);
  char string[] = "Hello World\n";
  struct Node * e = NULL;
  int c = 0;
  for (c = 0; c < strlen(string); ++c)
  {
      e = malloc(sizeof(struct Node));
      e->c = string[c];
      TAILQ_INSERT_TAIL(&head, e, nodes);
  }  
}

void showQueue()
{
  struct Node * e = NULL;
  TAILQ_FOREACH(e, &head, nodes)
  {
      printf("%c", e->c);
  }
}

void freeQueue()
{
  struct Node * e = NULL;
  while (!TAILQ_EMPTY(&head))
  {
      e = TAILQ_FIRST(&head);
      TAILQ_REMOVE(&head, e, nodes);
      free(e);
      e = NULL;
  }
}

int main (int arc, char * argv [])
{
  buildQueue();
  showQueue();
  freeQueue();
  return EXIT_SUCCESS;
}

主要操作

• TAILQ_INSERT_HEAD //从头插入
• TAILQ_INSERT_TAIL //从尾插入
• TAILQ_INSERT_AFTER
• TAILQ_INSERT_BEFORE
• TAILQ_FIRST
• TAILQ_LAST
• TAILQ_NEXT
• TAILQ_PREV
• TAILQ_REMOVE //给定node，将node从Tail Queue中删掉
• TAILQ_FOREACH //正向遍历
• TAILQ_FOREACH_REVERSE //逆向遍历
• TAILQ_INIT
• TAILQ_EMPTY

帮助生成的数据结构

(gdb) ptype head
type = struct head_s {
    struct Node *tqh_first;
    struct Node **tqh_last;
}

gdb) ptype *e
type = struct Node {
    char c;
    struct {
        struct Node *tqe_next;
        struct Node **tqe_prev;
    } nodes;
}