js数据结构和算法（二）栈和队列

jsummer 发布于2019-08-21 12:30 / 558人阅读

摘要：对于栈来说，这个表尾称为栈的栈顶，相应的表头称为栈底。栈和队列的区别栈的插入和删除操作都是在一端进行的，而队列的操作却是在两端进行的。出栈操作出栈操作就是在栈顶取出数据，栈顶指针随之下移的操作。

基本概念

栈和队列都是动态的集合，在栈中，可以去掉的元素是最近插入的哪一个。栈实现了后进先出。在队列中，可以去掉的元素总是在集合中存在的时间最长的那一个。队列实现了先进先出的策略。

栈的官方定义：栈（Stack）是一个后进先出（Last in first out,LIFO）的线性表，它要求只在表尾进行删除和插入操作。对于栈来说，这个表尾称为栈的栈顶，相应的表头称为栈底。入栈使用push()方法。出栈使用pop()方法。

最开始栈中不含有任何数据，叫做空栈，此时栈顶就是栈底。然后数据从栈顶进入，栈顶栈底分离，整个栈的当前容量变大。数据出栈时从栈顶弹出，栈顶下移，整个栈的当前容量变小。

我们把作用于队列上的INSERT操作称为入队（Enqueue），把作用于队列上的DELETE操作称为出队（Dequeue）。我们使用变量top来记录栈顶元素的位置和标记哪里可以加入新的元素，当向栈内压入元素时，该变量增大；从栈内弹出元素时，该变量减小。

栈和队列的区别

栈的插入和删除操作都是在一端进行的，而队列的操作却是在两端进行的。

typedef struct
{
    ElemType *base;
    ElemType *top;
    int stackSize;
}sqStack;

这里定义了一个顺序存储的栈，它包含了三个元素：base,top,stackSize。

其中base是指向栈底的指针变量，top是指向栈顶的指针变量，stackSize指示栈的当前可使用的最大容量。

创建一个栈

#define STACK_INIT_SIZE 100

initStack(sqStack *s)
{
    s->base = (ElemType *)malloc( STACK_INIT_SIZE * sizeof(ElemType) );
    if( !s->base )
        exit(0);

    s->top = s->base;   // 最开始，栈顶就是栈底
    s->stackSize = STACK_INIT_SIZE;
}

入栈操作

入栈操作又叫压栈操作，就是向栈中存放数据。

入栈操作要在栈顶进行，每次向栈中压入一个数据，top指针就要+1，知道栈满为止。

出栈操作

出栈操作就是在栈顶取出数据，栈顶指针随之下移的操作。

每当从栈内弹出一个数据，栈的当前容量就-1。

队列的顺序存储结构

入队列操作其实就是在队尾追加一个元素，不需要任何移动，时间复杂度为O(1)。

出队列则不同，因为我们已经架设下标为0的位置是队列的队头，因此每次出队列操作所有元素都要向前移动。

栈的方法和属性

push()：入栈操作
pop()：出栈操作（返回栈顶元素并删除t）
peak()：返回栈顶元素而不删除它
clear()：清除栈内所有元素
length()：记录栈内元素的个数
empty属性：表示栈内是否含有元素

栈的实现

function Stack(){
    this.dataStore = [];
    this.top = 0;
    this.push = push;
    this.pop = pop;
    this.peek = peek;
}

用一个数组dataStore来保存栈内元素，变量top记录栈顶位置

push()方法

先来实现push()方法，当向栈中压入一个新元素时，需要将其保存在数组中变量top对应的位置，然后将top值加1：

 function push(element){
        this.dataStore[this.top++] = element;//top值加1，指向下一个空位置
    }

pop()方法

function pop(){
    return this.dataStore[--this.top];//pop方法与push相反
}

peek()方法

peek方法返回数组的第一个top-1位置的元素，即栈顶元素：

function peek(){
    return this.dataStore[this.top-1];
}

length()方法

length方法通过返回变量top值的方法返回栈内的元素的个数：

function length(){
    return this.top;
}

clear()方法

将变量top的值设为0，就可以清空一个栈了：

function clear(){
    this.top = 0;
}

GPU云服务器云服务器栈和队列面试题栈和队列 c语言栈和队列的c语言 js算法和数据结构

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

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

js数据结构与算法--栈和队列

摘要：后入先出入栈使用方法，出栈使用方法入栈出栈出站队列队列是一种特殊的线性表，特殊之处在于它只允许在表的前端进行删除操作，而在表的后端进行插入操作，和栈一样，队列是一种操作受限制的线性表。 1.栈（stack）栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈...

ddongjian0000 2019-08-22 15:49 评论0 收藏0
CSS技巧

摘要：技巧使你的更加专业这是上关于技巧的一篇译文，另外你也可以在本项目看到原文。列举了一些很实用的技巧，比如给空内容的标签添加内容，逗号分隔列表等等。排序算法看源码，把它背下来吧排序算法的封装。主要帮助初学者更好的掌握排序算法的实现。成为专业程序员路上用到的各种优秀资料、神器及框架成为一名专业程序员的道路上，需要坚持练习、学习与积累，技术方面既要有一定的广度，更要有自己的深度。 Java...

DangoSky 2019-08-22 11:15 评论0 收藏0
CSS技巧

摘要：技巧使你的更加专业这是上关于技巧的一篇译文，另外你也可以在本项目看到原文。列举了一些很实用的技巧，比如给空内容的标签添加内容，逗号分隔列表等等。排序算法看源码，把它背下来吧排序算法的封装。主要帮助初学者更好的掌握排序算法的实现。成为专业程序员路上用到的各种优秀资料、神器及框架成为一名专业程序员的道路上，需要坚持练习、学习与积累，技术方面既要有一定的广度，更要有自己的深度。 Java...

zgbgx 2019-08-29 14:01 评论0 收藏0
JS数据结构与算法_链表

摘要：上一篇数据结构与算法栈队列下一篇数据结构与算法集合字典写在前面说明数据结构与算法系列文章的代码和示例均可在此找到上一篇博客发布以后，仅几天的时间竟然成为了我写博客以来点赞数最多的一篇博客。上一篇：JS数据结构与算法_栈&队列下一篇：JS数据结构与算法_集合&字典写在前面说明：JS数据结构与算法系列文章的代码和示例均可在此找到上一篇博客发布以后，仅几天的时间竟然成为了我写博客以...

NeverSayNever 2019-08-23 14:53 评论0 收藏0