栈与队列：实现与经典应用

// 运行环境：Node.js 14+
// 保存为 dsa-l6.js，执行：node dsa-l6.js

// 栈：数组 push/pop 即可（O(1) 均摊）
const stack = []
stack.push(1); stack.pop()

// 队列别用 shift（O(n)）！用"头指针"实现 O(1) 队列：
function createQueue() {
  const q = []
  let head = 0
  return {
    enqueue(x) { q.push(x) },
    dequeue() { return head < q.length ? q[head++] : undefined },
    size() { return q.length - head },
    isEmpty() { return head >= q.length }
  }
}

// 有效括号：遇到左括号入栈，右括号弹栈匹配
function isValid(s) {
  const map = { ')': '(', ']': '[', '}': '{' }
  const st = []
  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') st.push(ch)
    else if (st.pop() !== map[ch]) return false
  }
  return st.length === 0
}
console.log(isValid('()[]{}')) // true

function nextGreater(nums) {
  const res = new Array(nums.length).fill(-1)
  const st = [] // 存下标，栈底→栈顶 递减
  for (let i = 0; i < nums.length; i++) {
    while (st.length && nums[st[st.length - 1]] < nums[i]) {
      res[st.pop()] = nums[i] // 弹出的元素遇到"下一个更大"
    }
    st.push(i)
  }
  return res
}
console.log(nextGreater([2, 1, 2, 4, 3])) // [4, 2, 4, -1, -1]