数据结构 –栈与队列

栈（first in last out）

  • 栈的封装:

  • //封装栈类
        function Stack(){
            //栈中的属性
            this.items=[]
            //栈的相关操作
            //1.将元素压入栈
            Stack.prototype.push=function(element){
                this.items.push(element)
            },
            //2.从栈中取出元素
            Stack.prototype.pop=function(){
                return this.items.pop()
            },
            //3.查看一下栈顶元素
            Stack.prototype.peek=function(){
                return this.items[this.items.length -1]
            },
            //4.判断是否为空
            Stack.prototype.isEmpty=function(){
                return this.items.length==0
            },

            //5.获取元素个数
            Stack.prototype.size=function(){
                return this.items.length
            },
            //6.toString方法
            Stack.prototype.toString=function(){
                let resultString = ''
                for (let i=0;i<this.items.length; i++){
                    resultString += this.items[i]+''
                }
                return resultString
            }

        }
<!--hexoPostRenderEscape:<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line">* 栈的使用： </span><br><span class="line"></span><br><span class="line">* &#96;&#96;&#96;javascript</span><br><span class="line">  &#x2F;&#x2F;函数 ：十进制转成二进制</span><br><span class="line">          function dec2bin(decNumber) &#123;</span><br><span class="line">           &#x2F;&#x2F;1.定义栈对象</span><br><span class="line">              let stack&#x3D; new Stack()</span><br><span class="line">          &#x2F;&#x2F;2.循环操作</span><br><span class="line">              while (decNumber&gt;0)&#123;</span><br><span class="line">                  &#x2F;&#x2F;2.1获取余数，并且放到栈中</span><br><span class="line">                  stack.push(decNumber % 2)</span><br><span class="line">                  &#x2F;&#x2F;2.2获取整除后的结果 作为下次运行的数字</span><br><span class="line">                  decNumber&#x3D;Math.floor(decNumber&#x2F; 2 )</span><br><span class="line">              &#125;</span><br><span class="line">          &#x2F;&#x2F;3.从栈中取出0 和 1</span><br><span class="line">          let binaryString&#x3D;&#39;&#39;</span><br><span class="line">          while (!stack.isEmpty())&#123;</span><br><span class="line">                  binaryString +&#x3D; stack.pop()</span><br><span class="line">          &#125;</span><br><span class="line">          return binaryString</span><br><span class="line">          &#125;</span><br></pre></td></tr></table></figure>:hexoPostRenderEscape-->

  • 栈实现队列

  • function Squeue(){
        let stack1=[],stack2=[]
        Squeue.prototype.Senqueue=function(node){
            stack1.push(node)
        },
        Squeue.prototype.Sdequeue=function(){
            if(stack2.length>0){
               return stack2.pop()
            }else {
                while(stack1.length>0){
                stack2.push(stack1.pop())
                }
                return stack2.pop()

            }
        },
<!--hexoPostRenderEscape:<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line">  </span><br><span class="line"></span><br><span class="line">### 队列结构(FILO)</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"></span><br><span class="line">#### 队列的封装：</span><br><span class="line">![](https:&#x2F;&#x2F;lh3.googleusercontent.com&#x2F;proxy&#x2F;22AM0yZpzwydNKQmezZ6jPPsWoGj5SSmYG-FlGavh05ehxHIFIe0werYdr8h_c0yg6fWW1gOqwjhEapjlABgOS-RlebuGo1xpjejQzKCUdamRlOgiBwv77mvrQJV4O82bFJ0hnySA8l0GWVk2SXdIr6XPqzFKC4SNA8dwM5CZZ5v9ly7RKSbFR4sVCuugmrsfy4kMus)</span><br><span class="line">&#96;&#96;&#96;javascript</span><br><span class="line"> function Queue() &#123;</span><br><span class="line">    &#x2F;&#x2F;属性</span><br><span class="line">    this.items &#x3D; []</span><br><span class="line">    &#x2F;&#x2F;方法</span><br><span class="line">    &#x2F;&#x2F;1.将元素加入队列</span><br><span class="line">    Queue.prototype.enqeue &#x3D; function (element) &#123;</span><br><span class="line">      this.items.push(element)</span><br><span class="line">    &#125;</span><br><span class="line">    &#x2F;&#x2F;2.从队列中删除前端元素</span><br><span class="line">    Queue.prototype.dequeue &#x3D; function () &#123;</span><br><span class="line">      return this.items.shift()</span><br><span class="line">    &#125;</span><br><span class="line">    &#x2F;&#x2F;3.查看前端元素</span><br><span class="line">    Queue.prototype.front &#x3D; function () &#123;</span><br><span class="line">      return this.items[0]</span><br><span class="line">    &#125;</span><br><span class="line">    &#x2F;&#x2F;4.查看队列是否为空</span><br><span class="line">    Queue.prototype.isEmpty &#x3D; function () &#123;</span><br><span class="line">      return this.items.length &#x3D;&#x3D;&#x3D; 0</span><br><span class="line">    &#125;</span><br><span class="line">    &#x2F;&#x2F;5.查看队列中元素的个数</span><br><span class="line">    Queue.prototype.size &#x3D; function () &#123;</span><br><span class="line">      return this.items.length</span><br><span class="line">    &#125;</span><br><span class="line">    &#x2F;&#x2F;6.toString方法</span><br><span class="line">    Queue.prototype.toString &#x3D; function () &#123;</span><br><span class="line">      let resultString &#x3D; &#39;&#39;</span><br><span class="line">      for (let i &#x3D; 0; i &lt; this.items.length; i++) &#123;</span><br><span class="line">        resultString +&#x3D; this.items[i] + &#39;&#39;</span><br><span class="line">      &#125;</span><br><span class="line">      return resultString</span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br></pre></td></tr></table></figure>:hexoPostRenderEscape-->

击鼓传花

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//击鼓传花
function pass(nameList, num) {
  //1.创建队列结构
  let queue = new Queue()
  //2.将所有人一次加到队列中
  for(let i = 0; i<nameList.length;i++){
    queue.enqeue(nameList[i])
  }
  //3.开始数
  while (queue.size()>1){
    //不是num的时候 重新加入到队列的末尾
    //是num的这数字的时候 从队列删除
    //3.1num数字之前的人重新放入到队列的末尾
    for (let i=0;i<num-1;i++){
      queue.enqeue(queue.dequeue())
    }
    //3.2num对应的这个人从队列中删除
    queue.dequeue()
  }
  //4.获取剩下的那个人
  alert(queue.size())
  let endName = queue.front()
  alert('剩下的人：'+endName)
  return nameList.indexOf(endName)
}

  • 队列实现栈

  •  function QStack() {
            let queue = []

            QStack.prototype.Stackpush = function (node) {
                var len = queue.length;   //让len等于插入前的queue的长度 因为length会+1
                queue.push(node);
                for (var i = 0; i < len; i++) {   
                    queue.push( queue.shift());
                }
            },
                QStack.prototype.Stackpop = function () {
                    return queue.shift()
                },


              QStack.prototype.toString = function () {
                  let resultString = ''
                  for (let i = 0; i < queue.length; i++) {
                      resultString += queue[i] + ' '
                  }
                  return resultString
              }
      }