【数据结构】JavaScript实现堆栈和队列-蒲公英云

【数据结构】JavaScript实现堆栈和队列

以你之姓@ 2022-05-17 04:16 312阅读 0赞

栈： 又名堆栈，是一种遵循先进后出（LIFO）原则的线性表。只能在一端进行插入和删除操作。这一端被称为栈顶，相对地，把另一端叫做栈底。向一个栈插入新元素称为压栈，进栈；从一个栈删除元素叫做出栈，弹栈。
比如典型的例子：弹夹

创建栈，用一个js构造函数来表示栈

function Stack(){ 
        var items = []
         // 判断是不是空栈
        this.isEmporty = function(){ 
            return items.length == 0
        }
       // 压栈
        this.push = function(e){ 
            items.push(e)
            return items
        }
   // 出栈
        this.pop = function(){ 
            return items.pop()   
        }
       // 返回栈顶元素
        this.peek = function(){ 
            return items[items.length -1]
        }
       // 清空一个栈
        this.clear = function(){ 
            items = []
        }              
    }
    var stack = new Stack()
    console.log( stack.isEmporty() )
    console.log( stack.push(1) )
    console.log( stack.push(22) )
    console.log( stack.peek() )

用数组的方法实现的栈，比用C语言实现的栈简单多了

队列：是遵循FIFO（First In First Out，先进先出）的一种特殊的线性表。特殊在于只允许在表头进行删除元素（出队），在队尾添加新元素（进队）。

// 使用构造函数表示一个队列
        function Queue(){ 
            var items = []
            this.isEmpty = function(){ 
                return items.length == 0
            }
            // 入队操作，即在数组末尾添加一个元素，使用push()
            this.enqueue = function( e ){ 
               items.push(e)
               return items
            }
            // 出队,删除数组第一个元素，使用unshift()
            this.dequeue = function (){ 
                if( items == 0){
                    return '队空为....'
                }
                return items.unshift()
            }
            // 返回队列第一个元素
            this.front = function(){ 
                if( items == 0 ){
                    return '队空为....'
                }
                return items[0]
            }
            // 判断队列是否为空
            this.size = function(){ 
                return items.length;
            }
        }
        var dui = new Queue();
        console.log(dui.enqueue(2))
        console.log(dui.enqueue(2))
        console.log(dui.front())