《算法导论》笔记3-10

数据结构

栈（stack）

判断空栈：

stack_empty(S)
	return S.top == 0

压栈：

push(S, x)
	S.top++
	S[S.top] = x

弹栈：

pop(S)
	if stack_empty(S)
		error "underflow"
	else
		S.top--
		return S[S.top + 1]

队列（queue）

入队：

enqueue(Q, x)
	Q[Q.tail] = x
	if Q.tail == Q.length
		Q.tail = 1
	else
		Q.tail++

出队：

dequeue(Q, x)
	x = Q[Q.head]
	if Q.head == Q.length
		Q.head = 1
	else
		Q.head++
	return x 

链表（linked list）

搜索：

list_search(L, k)
	x = L.head
	while x != null and x.key != k
		x = x.next
	return x

插入：

list_insert(L, k)
	x.next = L.head
	if L.head != null
		L.head.prev = x
	L.head = x
	x.prev = null

删除：

list_delete(L, x)
	if x.prev != null
		x.prev.next = x.next
	else
		L.head = x.next
	if x.next != null
		x.next.prev = x.prev