陈恒承

栈

栈：一种专注于顶部元素进入进出的操作。

栈的应用

• 浏览器历史记录
• 代码的执行
• 正所谓空间换时间，有时候借助栈，我们能够缩短操作

简单的例子

关于栈的思考

栈就是一个后进先出的一个数据结构,一般解决问题，就要借助它的这种特性。

单调栈

为此栈的结构是递增或者递减的一种栈结构特性,求解”下一个大的数的”或者下一个小的问题”

一般的模版如下:

let stack = [];

let nums = [3, 2, 1, 5];

let result = [];

for (let i = nums.length - 1; i >= 0; i--) {
  while (stack.length !== 0 && nums[i] >= stack[stack.length - 1]) {
    stack.pop();
  }
  result.unshift(stack.length === 0 ? "null" : stack[stack.length - 1]);

  stack.push(nums[i]);
}

我们可以看到，这是从后到前的遍历，那么我们想从前到后呢？该怎么写呢？其实也简单

[2,7,4,3,5]

[7,0]
[7,0,5,5,0]

两栈模拟队列

function queue() {
  const stack1 = [];
  const stack2 = [];
}

queue.prototype.push = (val) => {
  const [from, to] = getFromAndToStack();
  from.push(val);
};

queue.prototype.getFromAndToStack = () => {
  const from = this.stack1.length >= 0 ? this.stack1 : this.stack2;
  const to = this.stack1.length < 0 ? this.stack1 : this.stack2;
  return [from, to];
};

queue.prototype.transform = (from, to) => {
  while (from.length > 0) {
    to.push(from.pop());
  }
};

queue.prototype.delete = (from, to) => {
  const [from, to] = getFromAndToStack();
  this.transform(from, to);
  to.pop();
};

class Queue {
  const stack1=[]
  const stack2=[];

  push(val){
     this.stack1.push(val)
  }

  delete(){
   if(this.stack2.length===0){

     while(this.stack1.length>0){
          this.stack2.push(this.stack1.pop())
     }
   }

   if(this.stack2.length===0){
     throw new Error('queue is empty')
   }

   const val=stack2.pop()

   return val
  }
}

两个队列模拟栈

class Stack {

   const queue1=[];
   const queue2=[];

   add(el){
     this.queue1.push(el)
   }

   delete(){
     if(this.queue2.length===0){
         while(this.queue1.length>0){
           this.queue2.push(this.queue1.shift())
         }
     }

     if(this.queue2.length===0){
      throw new Error('stack is empty')
     }

     return this.queue2.shift()
   }

}

为什么 right=mid+1,left=mid 是因为 检查的时候，arr[mid]的值在不在我们的区间内

function test(arr, n) {
  let right = arr.length - 1;
  let left = 0;
  let mid = 0;
  if (arr.length === 1) return arr[0];

  while (left < right) {
    mid = Math.floor((right + left) / 2);
    if (arr[mid] > arr[right]) {
      right = mid + 1;
    } else if (arr[mid] < arr[right]) {
      left = mid;
      // 相等情况下
    } else {
      //
      right--;
    }
  }

  return arr[left];
}