My Little World

队列

发表于

队列

1.先进先出的线性表，有顺序表和链表
2.只允许在一段插入，另一端删除

队列的链式存储结构

和栈相反，队列常用链表实现

1
2
3
4
5
6
7
8
typedef sruct QNode{
	ElemType data;
	struct QNode *next;
}QNode,*QueuePrt;
typedef struct {
	QueuePrt front;	##队头指针指向链队列的头结点(头结点不是必要的)
	QueuePrt rear;	##队尾指针指向终端结点，空队列时，front，rear都指向头结点
}LinkQueue;

queue1
queue2

入队列

queue3

1
2
3
4
5
6
7
8
9
10
11
InsertQueue(LinkQueue *q,ElemType e){
	QueuePrt p;
	p = (QueuePtr)malloc(sizeof(QNode));
	if(p==NULL){
		exit(0);
	}
	p->data = e;
	p->next = NULL;
	q->rear->next = p;
	q->rear = p;
}

出队列

queue5
queue6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
DeleteQueue(LinkQueue *q,ElemType e){
	QueuePrt p;
	if(q->front ==q->rear)
	{
		retrun;
	}
	p=q->front->next;
	*e=p->data;
	q->front->next = p->next;
	if(q->rear ==p){
		q->rear = q->front;
	}
	free(p);
}

销毁一个队列

由于链队列建立在内存的动态区，因此当一个队列
不在有用时，应当及时销毁掉，以免过多占用内存空间

1
2
3
4
5
6
7
DestroyQueue(LinkQueue *q){
	while(q->front){
	q->rear = q->front->next;
	free(q->front):
	q->front = q->rear;
	}
}

简单实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var list = [];
for(var i=0;i<5;i++){
  list.push({
    next:i+1
  })
}
list[4].next = null;
console.log(list);
//入队列
var length = list.length;
list.push({
  next:null
})
list[length-1].next=length;
console.log(list);
//出队列
list.splice(0,1);
console.log(list);
//清空
list=[];