js数据结构和算法(二)栈和队列


基本概念

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

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

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

js数据结构和算法(二)栈和队列

我们把作用于队列上的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。

队列的顺序存储结构

js数据结构和算法(二)栈和队列

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

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

js数据结构和算法(二)栈和队列

栈的方法和属性

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;
}

4 responses on “js数据结构和算法(二)栈和队列

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>