На этом шаге мы приведем общие сведения об очередях.

    Очередью будем называть списочную структуру, состоящую из некоторого списка и лисповской ячейки, содержащей указатели на первый и последний элементы этого списка [1, с.134].

    На рисунках изображены очереди, состоящие из элементов:

• A

  
  Рис.1. Первый пример очереди

• A,B

  
  Рис.2. Второй пример очереди

   (DEFUN TCONC (LAMBDA (X Q)
   ; Добавление элемента X к очереди Q ;
      (COND ( (NULL Q) (CONS (SETQ Q (CONS X NIL)) Q) )
            (    T     (RPLACD Q (CDR (RPLACD (CDR Q)
                                              (CONS X NIL))))
            )
      )
   ))

    Тестовые примеры:

   $ (SETQ Q (TCONC A NIL))
   ((A) A)
   $ (TCONC B Q)
   ((A B) B)

    Внутреннее представление значения очереди Q после вычисления первого выражения изображено на рис. а), а после второго - на рис b).

    Заметим, что доступ к первому элементу очереди Q дает функция (CAAR Q), а к последнему - (CADR Q).

   $ (CAAR Q)
   A
   $ (CADR Q)
   B

    Исключить из очереди Q первый (но не единственный) элемент можно с помощью обращения (RPLACA Q (CDAR Q)):

   $ (RPLACA Q (CDAR Q))
   ((A) A)

   (DEFUN QUEUE (LAMBDA (LST)
   ; Построение очереди из списка LST ;
      (LIST LST (LAST LST))
   ))
   ; --------------------- ;
   (DEFUN LAST (LAMBDA (LST)
   ; Функция LAST возвращает последний элемент ;
   ;              списка LST                   ;
      (COND ( (NULL LST) NIL )
            ( (NULL (CDR LST)) (CAR LST) )
            (        T         (LAST (CDR LST)) )
      )
   ))

    На следующем шаге мы рассмотрим функции для построения очереди.

Предыдущий шаг Содержание Следующий шаг