最近在学习typescript，就想着用typescript自己练习一些基本的数据结构，记录一下，读者有什么想法和建议也可以交流一下。

栈

class Stack<T>{
    private items = null;
    constructor() {
        this.items = new Array<T>();
    }
    push(data: T): void {
        this.items.push(data);
    }
    pop(): T {
        return this.items.pop();
    }
    top(): T {
        return this.items[this.items.length - 1];
    }
    isEmpty(): boolean {
        return this.items.length === 0;
    }
    size(): number {
        return this.items.length;
    }
    clear(): void {
        this.items = new Array<T>();
    }
    print(): void {
        console.log(this.items);
    }
}

队列

class Queue<T>{
    private items = null;
    constructor() {
        this.items = new Array<T>();
    }
    enqueue(data: T): void {
        this.items.push(data);
    }
    dequeue(): T {
        return this.items.shift();
    }
    head(): T {
        return this.items[0];
    }
    size(): number {
        return this.items.length;
    }
    clear(): void {
        this.items = new Array<T>();
    }
    isEmpty(): boolean {
        return this.items.length === 0;
    }
    tail(): T {
        return this.items[this.items.length - 1];
    }
    print(): void {
        console.log(this.items);
    }
}

链表

class LinkNode<T>{
    public data: T;
    public next: LinkNode<T>;
    constructor(data: T) {
        this.data = data;
        this.next = null;
    }
}

class LinkList<T>{
  private head: Node<T>;
  private length: number;
  private tail: Node<T>;
  constructor() {
    this.head = null;
    this.tail = null;
  }

  append(data: T): boolean {
    let new_node = new Node(data);
    if (this.head == null) {
      this.head = new_node
      this.tail = new_node;
    } else {
      this.tail.next = new_node;
      this.tail = this.tail.next;
    }
    this.length++;
    return true;
  }

  len(): number {
    return this.length;
  }

  insert(index: number, data: T): boolean {
    if (index == this.length) {
      return this.append(data);
    } else {
      let insert_index = 1;
      let cur_node = this.head;
      while(insert_index < index) {
        cur_node = cur_node.next;
        insert_index++;
      }
      let next_node = cur_node.next;
      let new_node = new Node(data);
      cur_node.next = new_node;
      cur_node.next.next = next_node;
    }
    this.length++;
    return true;
  }

  remove(index): Node<T> {
    if (index < 0 || index >= this.length) {
      return null;
    } else {
      let del_node = null;
      if (index == 0) {
        del_node = this.head;
        this.head = this.head.next;
      } else {
        let del_index = 0;
        let pre_node = null;
        let cur_node = this.head;
        while (del_index < index) {
          del_index++;
          cur_node = cur_node.next;
        }
        pre_node = cur_node;
        cur_node = cur_node.next;
        pre_node.next = cur_node;
        //如果删除的是尾节点
        if (cur_node == null) {
          this.tail = pre_node;
        }
        this.length--;
        return del_node;
      }
    }
  }

  get(index): Node<T> {
    if (index < 0 || index > this.length) {
      return null;
    }
    let node_index = 0;
    let cur_node = this.head;
    while(node_index < index) {
      node_index++;
      cur_node = cur_node.next;
    }
    return cur_node;
  }

  print(): void {
    let cur = this.head;
    while(cur != null) {
      console.log(cur.data);
      cur = cur.next;
    }
  }

}