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

以你之姓@ 2022-05-17 04:16 238阅读 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())