Structures de données avancées

Implémentation de structures de données efficaces: listes chaînées, piles, files, arbres, graphes. Essentielles pour résoudre des problèmes algorithmiques complexes.

Pile (Stack)

-- Structure de pile (LIFO - Last In First Out)
local Stack = {}
Stack.__index = Stack

function Stack.new()
  return setmetatable({items = {}, top = 0}, Stack)
end

function Stack:push(value)
  self.top = self.top + 1
  self.items[self.top] = value
end

function Stack:pop()
  if self.top == 0 then return nil end
  local value = self.items[self.top]
  self.items[self.top] = nil
  self.top = self.top - 1
  return value
end

function Stack:peek()
  return self.items[self.top]
end

function Stack:isEmpty()
  return self.top == 0
end

function Stack:size()
  return self.top
end

-- Utilisation
local pile = Stack.new()
pile:push(10)
pile:push(20)
pile:push(30)
print(pile:pop())  -- 30
print(pile:peek()) -- 20
print(pile:size()) -- 2

File (Queue)

-- Structure de file (FIFO - First In First Out)
local Queue = {}
Queue.__index = Queue

function Queue.new()
  return setmetatable({items = {}, front = 1, back = 0}, Queue)
end

function Queue:enqueue(value)
  self.back = self.back + 1
  self.items[self.back] = value
end

function Queue:dequeue()
  if self.front > self.back then return nil end
  local value = self.items[self.front]
  self.items[self.front] = nil
  self.front = self.front + 1
  return value
end

function Queue:peek()
  return self.items[self.front]
end

function Queue:isEmpty()
  return self.front > self.back
end

function Queue:size()
  return self.back - self.front + 1
end

-- Utilisation
local file = Queue.new()
file:enqueue("A")
file:enqueue("B")
file:enqueue("C")
print(file:dequeue())  -- A
print(file:dequeue())  -- B
print(file:size())     -- 1

Liste chaînée

-- Nœud de liste chaînée
local Node = {}
Node.__index = Node

function Node.new(value)
  return setmetatable({value = value, next = nil}, Node)
end

-- Liste chaînée
local LinkedList = {}
LinkedList.__index = LinkedList

function LinkedList.new()
  return setmetatable({head = nil, tail = nil, length = 0}, LinkedList)
end

function LinkedList:append(value)
  local node = Node.new(value)
  if not self.head then
    self.head = node
    self.tail = node
  else
    self.tail.next = node
    self.tail = node
  end
  self.length = self.length + 1
end

function LinkedList:prepend(value)
  local node = Node.new(value)
  node.next = self.head
  self.head = node
  if not self.tail then
    self.tail = node
  end
  self.length = self.length + 1
end

function LinkedList:toArray()
  local arr = {}
  local current = self.head
  while current do
    table.insert(arr, current.value)
    current = current.next
  end
  return arr
end

function LinkedList:find(value)
  local current = self.head
  local index = 1
  while current do
    if current.value == value then
      return index, current
    end
    current = current.next
    index = index + 1
  end
  return nil
end

-- Utilisation
local liste = LinkedList.new()
liste:append(10)
liste:append(20)
liste:prepend(5)
for _, v in ipairs(liste:toArray()) do
  print(v)  -- 5, 10, 20
end

Arbre binaire de recherche

-- Nœud d'arbre
local TreeNode = {}
TreeNode.__index = TreeNode

function TreeNode.new(value)
  return setmetatable({
    value = value,
    left = nil,
    right = nil
  }, TreeNode)
end

-- Arbre binaire de recherche
local BST = {}
BST.__index = BST

function BST.new()
  return setmetatable({root = nil, size = 0}, BST)
end

function BST:insert(value)
  local function insertNode(node, value)
    if not node then
      self.size = self.size + 1
      return TreeNode.new(value)
    end
    
    if value < node.value then
      node.left = insertNode(node.left, value)
    elseif value > node.value then
      node.right = insertNode(node.right, value)
    end
    
    return node
  end
  
  self.root = insertNode(self.root, value)
end

function BST:search(value)
  local function searchNode(node, value)
    if not node then return false end
    if value == node.value then return true end
    if value < node.value then
      return searchNode(node.left, value)
    else
      return searchNode(node.right, value)
    end
  end
  
  return searchNode(self.root, value)
end

function BST:inorder()
  local result = {}
  local function traverse(node)
    if not node then return end
    traverse(node.left)
    table.insert(result, node.value)
    traverse(node.right)
  end
  traverse(self.root)
  return result
end

-- Utilisation
local arbre = BST.new()
arbre:insert(50)
arbre:insert(30)
arbre:insert(70)
arbre:insert(20)
arbre:insert(40)
print(arbre:search(30))  -- true
print(arbre:search(100)) -- false
for _, v in ipairs(arbre:inorder()) do
  print(v)  -- 20, 30, 40, 50, 70
end