Piles et files : LIFO contre FIFO

Deux ordres de traitement opposés à reconnaître dès l'énoncé.

• Pile (stack) : dernier entré, premier sorti. push / pop du même côté, en O(1).
• File (queue) : premier entré, premier sorti. enqueue d'un côté, dequeue de l'autre, en O(1).

Parenthèses valides#

Chaque fermante doit correspondre à la dernière ouvrante non fermée : c'est exactement une pile.

function isValid(s: string): boolean {
  const pairs: Record<string, string> = { ")": "(", "]": "[", "}": "{" };
  const stack: string[] = [];
  for (const c of s) {
    if (c in pairs) {
      if (stack.pop() !== pairs[c]) return false;
    } else {
      stack.push(c);
    }
  }
  return stack.length === 0;
}

Pile monotone : prochain élément plus grand#

On garde des indices dont les valeurs sont décroissantes ; un nouvel élément plus grand « résout » tous ceux qu'il dépasse. Chaque indice entre et sort une fois : O(n) au lieu de O(n²).

function nextGreater(nums: number[]): number[] {
  const result = new Array<number>(nums.length).fill(-1);
  const stack: number[] = [];                       // indices, valeurs décroissantes
  for (let i = 0; i < nums.length; i++) {
    while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
      result[stack.pop()!] = nums[i];
    }
    stack.push(i);
  }
  return result;
}

Piège : en JavaScript, utiliser un tableau comme file avec shift() coûte O(n) (tous les éléments sont décalés). Pour une vraie file, gardez un index de tête, ou utilisez une liste chaînée / deque (collections.deque en Python).

Pour aller plus loin#

• Data structures: Introduction to stack — mycodeschool
• Data structures: Introduction to Queues — mycodeschool