资讯专栏INFORMATION COLUMN

TypeScript实现数据结构(一)栈,队列,链表

qujian / 3159人阅读

摘要:最近在学习,就想着用自己练习一些基本的数据结构,记录一下,读者有什么想法和建议也可以交流一下。栈队列链表如果删除的是尾节点

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

class Stack{
    private items = null;
    constructor() {
        this.items = new Array();
    }
    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();
    }
    print(): void {
        console.log(this.items);
    }
}
队列
class Queue{
    private items = null;
    constructor() {
        this.items = new Array();
    }
    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();
    }
    isEmpty(): boolean {
        return this.items.length === 0;
    }
    tail(): T {
        return this.items[this.items.length - 1];
    }
    print(): void {
        console.log(this.items);
    }
}


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

class LinkList{
  private head: Node;
  private length: number;
  private tail: Node;
  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 {
    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 {
    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;
    }
  }

}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/101578.html

相关文章

  • JavaScript 数据结构与算法之美 - 线性表(数组、队列链表

    摘要:每个线性表上的数据最多只有前和后两个方向。数组链表队列栈等就是线性表结构。非线性表数据之间并不是简单的前后关系。不包含任何元素的栈称为空栈。移除栈顶的元素,同时返回被移除的元素。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 前言 基础知识就像是一座大楼的地基,它决定了我们的技术高度。 我们应该多掌握一些可移值的...

    kaka 评论0 收藏0
  • 队列 - Algorithms, Part I, week 2 STACKS AND QUEUE

    摘要:在改进前使用数组的一个缺点是必须声明数组的大小,所以栈有确定的容量。待解决的问题建立一个能够增长或者缩短到任意大小的栈。下边的图是观察时间开销的另一种方式,表示了入栈操作需要访问数组的次数。 前言 上一篇:算法分析下一篇:基本排序 本篇内容主要是栈,队列 (和包)的基本数据类型和数据结构文章里头所有的对数函数都是以 2 为底关于性能分析,可能还是需要一些数学知识,有时间可以回一下在很多...

    Stardustsky 评论0 收藏0
  • 【Java实现队列就是这么简单

    摘要:一前言上一篇已经讲过了链表实现单向链表了,它跟数组都是线性结构的基础,本文主要讲解线性结构的应用栈和队列如果写错的地方希望大家能够多多体谅并指正哦,如果有更好的理解的方式也希望能够在评论下留言,让大家学习学习二数据结构栈就是这么简单数据结构 一、前言 上一篇已经讲过了链表【Java实现单向链表】了,它跟数组都是线性结构的基础,本文主要讲解线性结构的应用:栈和队列 如果写错的地方希望大家...

    Ethan815 评论0 收藏0
  • 图解几种常见的线性表

    摘要:下面来看一下,有哪些数据结构属于线性表吧栈特性先进后出只有唯一的一个出入口介绍栈又名堆栈,它是一种运算受限的线性表。 原文是在我自己博客中,小伙伴也可以点阅读原文进行跳转查看,还有好听的背景音乐噢背景音乐已取消~ 2333333 线性表 什么是线性表?就是一种连续或间断存储的数组,这里的连续和间断是针对物理内存空间中线性表元素之间是否连续,其中连续数组对应内置数组的实现方式,间断数组对...

    wawor4827 评论0 收藏0

发表评论

0条评论

qujian

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<