数据结构之链表--栈--队列

链表知识点：
1. 头结点是在链表的开始结点之前附加的一个结点，他的数据域可以为空，也可以是存储线性表的长度等附加信息。它具有两个优点:
（1）、由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和 在表的其它位置上操作一致,无须进行特殊处理;（2）、无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表 的处理也就统一了。

2. 双向链表相关的操作：
http://blog.csdn.net/fjb2080/article/details/5457609

struct list_head{

struct list_head *next, *prev;

};

定义一个双向链表的头节点，我们可以这样：

 #define LIST_HEAD_INIT(name) { &(name), &(name) }

struct list_head head;

LIST_HEAD_INIT(head);

list_head 的遍历的宏 如果有删除元素的遍历，请用第二个宏

/**

* list_for_each - iterate over a list

* @pos: the &struct list_head to use as a loop counter.

* @head: the head for your list.

*/

#define list_for_each(pos, head) /

for (pos = (head)->next; pos != (head); pos = pos->next)

 

/**

* list_for_each_safe - iterate over a list safe against removal of list entry

* @pos: the &struct list_head to use as a loop counter.

* @n: another &struct list_head to use as temporary storage

* @head: the head for your list.

*/

#define list_for_each_safe(pos, n, head) /

for (pos = (head)->next, n = pos->next; pos != (head); /

pos = n, n = pos->next)

删除元素之后要重新将删除了的元素进行初始化，因为他的prev和next都已经失去了意义。

/**

* list_del_init - deletes entry from list and reinitialize it.

* @entry: the element to delete from the list.

*/

static __inline__ void list_del_init(struct list_head *entry)

{

__list_del(entry->prev, entry->next);

INIT_LIST_HEAD(entry);

}

linux源代码中的一个例子：
struct pnp_card {
    struct device dev;        /* Driver Model device interface */
    unsigned char number;        /* used as an index, must be unique */
    struct list_head global_list;    /* node in global list of cards */
}
这样就实现了一个元素可以加入很多条 链表的例子


栈知识点：

1. 栈的top最开始的时候是和base在同一个位置的，当push一次之后就会变成top多加了一个，也就因此导致GetTop的时候需要S.top -1

2.  栈和对列都是一些工具而已，所以一般情况下，都是初始化时为空，然后在条件结束的时候也为空。

队列知识点：

1.只是一种FIFO的线性表，能插入的一端叫队尾，能删除的一端叫队头。
   注意： 一般的实现中也会在最前面插入一个 头结点，所以在DeQueue的时候会有一个特殊情况，就是在只有一个实际节点的时候出队列，记得要跟新Q.rear