TypeScript实现数据结构（一）栈，队列，链表

男娘i 2022-03-08 15:15 343阅读 0赞

最近在学习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;
        }
      }
    
    }