# 栈和队列

## 栈

class Stack
def initialize
@elements = []
end

def empty
@elements.size == 0
end

def push(x)
@elements[@elements.size] = x
end

def pop
raise "Cannot pop empty stack!" if @elements.size < 0
result = @elements[@elements.size - 1]
@elements[@elements.size - 1] = nil
result
end

end


## 队列

class Queue

def initialize
@elements = []
end

def enqueue(x)
@elements[@elements.size] = x
end

def dequeue
raise "Queue is empty!" if @elements.size == 0
result = @elements.shift
result
end

end


# 链表

• 如果一个链表是单链接的, 则省略每个元素中的 prev 指针.
• 如果链表是已排序的, 则链表的线性顺序与链表元素中关键字的线性顺序一直.
• 如果链表是未排序的, 则表中的元素可以以任何顺序出现.
• 如果链表是循环链表, 表头元素的 prev 指针指向表尾元素, 而表尾元素的 next 指针指向表头元素.
class LinkList
attr_accessor :head

def initialize
@head = nil
end

def search(key)
x = @head
while x != nil && x.value != key
x = x.next
end
x
end

def insert(node)
node.next = @head
@head.prev = node if @head != nil
@head = node
node.prev = nil
end

def delete(node)
if node.prev != nil
node.prev.next = node.next
else
@head = node.next
end
node.next.prev = node.prev if node.next != nil
end

end

class Node
attr_accessor :prev, :value, :next

def initialize(value)
@prev = nil
@value = value
@next = nil
end

end


def search(key)
x = @head
while x != nil && x.value != key
x = x.next
end
x
end


def insert(node)
node.next = @head
@head.prev = node if @head != nil
@head = node
node.prev = nil
end


def delete(node)
if node.prev != nil
node.prev.next = node.next
else
@head = node.next
end
node.next.prev = node.prev if node.next != nil
end


# 树

## 二叉树

comments powered by Disqus