Введение

Очередь является абстрактным типом данных , где элементы добавляются к передним (Enqueue) и удалены от задней (DEQUEUE). Это также известно как принцип FIFO (First In First Out) .

Лучше всего это показать на примере:

Вызов

Учитывая непустой массив, который содержит положительные целые числа и элементы, которые указывают на очередь (удаление элемента), выведите окончательный список очереди.

Допустим, это Xобозначает dequeue в этом примере. Давайте посмотрим на следующий список:

[45, X, X, 37, 20, X, 97, X, 85]

Это может быть переведено в следующий псевдокод очереди:

                   Queue
Enqueue 45    ->   45
Dequeue       ->   
Dequeue       ->              (dequeue on an empty queue is a no-op)
Enqueue 37    ->   37
Enqueue 20    ->   20 37
Dequeue       ->   20
Enqueue 97    ->   97 20
Dequeue       ->   97
Enqueue 85    ->   85 97

Вы можете видеть, что в итоге получается результат [85, 97], который является выходом для этой последовательности.

Контрольные примеры

Обратите внимание, что вы можете выбрать любой другой символ или символ X, если он не является положительным целым числом.

[1, X, 2, X, 3, X]      ->     []
[1, 2, X]               ->     [2]
[1, 2, 3]               ->     [3, 2, 1]
[1, 2, X, X, X, 3]      ->     [3]
[1, 2, X, 3, X, 4]      ->     [4, 3]

Это код-гольф , поэтому выигрывает представление с наименьшим количеством байтов!

Желе , 8 байт

F;@Ṗṛ?¥/

Использует любое ложное значение ( 0 или пустое итерируемое) для удаления из очереди.

Попробуйте онлайн!

Как это работает

F;@Ṗṛ?¥/  Main link. Argument: A (array)

       /  Reduce A by the link to the left.
      ¥     Combine the two links to the left into a dyadic chain.
F             Flatten the left argument.
    ṛ?        If the right argument is truthy:
 ;@             Concatenate the right argument and the flattened left argument.
              Else:
   Ṗ            Pop; remove the last element of the flattened left argument.
                This is why flattening is required, as Ṗ doesn't handle integers
                as intended for this challenge.

Python 2, 56 53 50 байт

q=[]
for i in input():q=[[i]+q,q[:i]][i<0]
print q

Попробуйте онлайн!

Dequeue есть -1. Этот трюк позволяет легко питонировать нарезку очереди.

Mathematica, 102 байта

Определенно, это не самое короткое решение, но я не смог устоять, потому что это своего рода извращение.

r=Reverse@{##}&
a_~f~b___:=b
f[a_,b___,]:=b
ToExpression[{"r[","f["~Table~StringCount[#,"]"],#}<>"]"]&

После некоторых вспомогательных функций это определяет чистую функцию, которая принимает строку в качестве входных данных: в строке числа разделяются запятыми (пробел необязательный); символ dequeue является "]"; и в списке нет разделителей спереди или сзади. Например, первый пример в OP будет введен как строка "45,],],37,20,],97,],85". Вывод функции представляет собой список чисел.

Функция подсчитывает, сколько очереди "]"находится во входной строке, добавляет столько копий "f["к началу строки, а затем окружает все это "r[...]". В приведенном выше примере это производит "r[f[f[f[f[45,],],37,20,],97,],85]"; обратите внимание, что скобки сбалансированы.

Затем ToExpressionинтерпретирует полученную строку как часть кода Mathematica и выполняет ее. Функция fудобно определена, чтобы сохранить все свои аргументы, кроме первого (и также игнорирует конечные запятые; в любом случае, это необходимо для удаления пустых очередей), и rпреобразует полученную последовательность чисел в список чисел в правильном порядке.

Сетчатка , 30 байт

1+`\d+,(.*?)X,?|^X,
$1
O^$`\d+

Попробуйте онлайн!

Повторно удаляет первое число, которое (не обязательно сразу), сопровождаемое Xвместе с этим X, или Xв начале строки. Затем переворачивает оставшиеся числа.

JavaScript, 70 63 53 50 43 байта

Спасибо @Neil за вывод 10 байтов с x.map вместо цикла и троичного выражения

Спасибо @Arnauld за 3 байта

Спасибо @ETHproductions за игру в 7 байтов

x=>(t=[],x.map(a=>+a?t=[a,...t]:t.pop()),t)

Попробуйте онлайн!

Исключением может быть любое нечисловое значение, кроме true.

Mathematica, 46 45 байт

Спасибо ngenisis за сохранение 1 байта.

Reverse[#//.{_Integer:0,a___,X,b___}:>{a,b}]&

В основном так же, как мой ответ Retina, используя сопоставление с образцом. Мы повторно сопоставляем первое Xи удаляем его вместе с первым числом (если оно существует). После того как мы закончим, мы перевернем список.

Чистый Баш, 72

Ввод дан как параметры командной строки.

for a;{
[ ${a/X} ]&&q=(${a:n++,0} ${q[@]})||((n-=n>0))
}
echo ${q[@]::n}

Попробуйте онлайн .

Haskell, 41 байт

x&y:z|y<1=init x&z|w<-y:x=w&z
x&y=x
([]&)

MATL , 13 12 байт

vi"@?@wh}IL)

Ввод представляет собой массив чисел, с 0для "dequeue".

Выходные данные разделены пробелами. Пустой результат отображается как ничто.

Попробуйте онлайн! Или проверьте все тестовые случаи .

объяснение

v        % Concatenate stack contents: gives []. This will grow to represent the queue
i        % Input numeric array
"        % For each entry in the input array
  @?     %   If current entry is non-zero
    @wh  %     Prepend current entry to the queue
  }      %   Else
    IL)  %     Remove last element from the queue
         %   End (implicit)
         % End (implicit)
         % Display (implicit)

Haskell, 41 40 байт

l#a|a>0=a:l|l>[]=init l|1>0=l

Функция foldl(#)[](также включена в bytecount с разделительным байтом)

Попробуйте онлайн!

X - любое неположительное целое число

РЕДАКТИРОВАТЬ: -1 байт благодаря Ними

Юлия, 78 76 73 57 байт

f(a)=(q=[];[x<1?q=q[2:end]:push!(q,x)for x=a];reverse(q))

Спасибо Харрисону Гродину за отличные советы по игре в гольф от Юлии. Заменяется if / else на троичный, а for / заканчивается на понимание списка для экономии 16 байт.

f(a)=(q=[];for x in a if x<1 q=q[2:end]else q=[q...,x]end end;reverse(q))

Убраны некоторые ненужные места для экономии 3 байта.

До того как отрицательные числа или ноль были разрешены:

f(a)=(q=[];for x in a if x==:X q=q[2:end] else q=[q...,x] end end;r everse(q))

Ungolfed:

function dequeue(list)
    queue = []

    for x in list
        if x < 1
            queue = queue[2:end]
        else
            queue = [queue..., x]
        end
    end

    reverse(queue)
end

Я довольно новичок в Джулии; Там может быть лучший способ. Использует :Xдля X, который является символом в Юлии. Обновлено: теперь, когда 0 разрешено, использует 0 (или любое отрицательное число) для X, сохраняя два символа. Обновил снова, чтобы удалить некоторые пробелы, которые я не понимал, не было необходимости.

05AB1E , 12 11 байт

Сохраненный байт благодаря Райли

)Evyai¨ëy¸ì

Попробуйте онлайн!

объяснение

Dequeues обозначаются любой буквой .

)             # wrap stack in a list (pushes empty list)
 Ev           # for each y in evaluated input
   yai        # if y is a letter
      ¨       # remove the first element of the list
       ëy¸ì   # else, prepend y to the list

GNU Sed, 43

Оценка включает +2 за использование -rи -nфлагов.

G
s/X\n( *|(.*)\b\S+ *)$/\2/
s/\n/ /
h
$p

Попробуйте онлайн .

объяснение

                            # Implicitly read the next line
G                           # append a newline, then the contents of the hold space
s/X\n( *|(.*)\b\S+ *)$/\2/  # If the input was an X, remove it, the newline, and any element at the end
s/\n/ /                     # Otherwise if the input was not an X, it is simply enqueued by removing the newline between it and the rest of the line
h                           # save a copy of the queue to the hold space
$p                          # since we're using -n to suppress output at the end of processing each input line, then this explicit print is required in the last line

PHP, 85 байт

<?$r=[];foreach($_GET as$v)is_int($v)?array_unshift($r,$v):array_pop($r);print_r($r);

-8 байт $vвместо, is_int($v)если каждое значение в очереди относится к ложному

Python 3 , 95 94 байта

def f(x):q=[];[*map(lambda s:exec(("q.pop(0)"if q else"","q+=[s]")[s!="X"]),x)];print(q[::-1])

Попробуйте онлайн!

Также 94 байта:

def f(x):q=[];[*map(lambda s:exec((("","q.pop(0)")[q>[]],"q+=[s]")[s!="X"]),x)];print(q[::-1])

Perl 5 , 28 + 1 = 29 байт

28 байт кода + -pфлаг.

/\d/?$\=$_.$\:$\=~s/.*
$//}{

Попробуйте онлайн!

Он использует строку ( $\) в качестве очереди: когда вход содержит целое число ( /\d/?мы добавляем его в начале $\( $\=$_.$\), а в противном случае мы удаляем последний с s/.*\n$//. В конце, $\неявно печатается благодаря -pflag (и те, которые не имеют себе равных }{).

Другие подходы:

• 33 байта , используя массив в качестве очереди (я думаю, это самый естественный способ сделать это на Perl, но не самый короткий):

  /X/?pop@F:unshift@F,$_}{$_="@F"

  Попробуйте онлайн!

• 52 байта , используя регулярное выражение и reverse(это, в общем-то, то же самое, что ответ Retina Мартина Эндера - благодаря которому я сэкономил на нем 2 байта). Обратный список занимает много символов, потому что, чтобы сохранить целые числа, мне нужно преобразовать строку в массив, чтобы обратить его обратно, а затем обратно в строку, чтобы распечатать. ( say forвместо того, чтобы $_=join$",сохранить 2 байта, но это требует -Eили -M5.010и это не так интересно).

  s/\d+ (.*?)X ?|^X/$1/&&redo;$_=join$",reverse split

  Попробуйте онлайн!

Python 3, 107 байт

def f(x):
 r = []
 for i in x:exec("try:r.pop(0)\nexcept:8;r+=i,".split(";")[type(i)==int])
 return r[::-1]

Dequeuer может иметь любое нечисловое значение.

Попробуйте онлайн

Пакетный, 160 байт

@set s=.
@for %%n in (%*)do @if %%n==X (call set s=%%s:* =%%)else call set s=%%s:~,-1%%%%n .
@set t=
@for %%n in (%s:~,-1%)do @call set t= %%n%%t%%
@echo%t%

Это было сложнее, чем нужно было.

• Хотя Batch может перечислять результат разбиения строки, он не может легко удалить элемент из перечисления.
• Он может удалить первый элемент, но только если есть хотя бы один элемент. В противном случае вы получите мусор.

Это означает, что я а) должен иметь маркер конца очереди, который не удаляется, и б) должен манипулировать очередью задом наперед, чтобы новые элементы вставлялись непосредственно перед маркером конца, так что старые элементы могут быть удалены с лицевой стороны, что означает, что я c) должен перевернуть очередь перед печатью.

PHP, 70 байт

foreach($argv as$v)+$v?$r[]=$v:array_shift($r);krsort($r);print_r($r);

C #, 115 байт +33 байта за использование

l=>{var r=new List<int>();foreach(var n in l)if(n<0)try{r.RemoveAt(0);}catch{}else r.Add(n);r.Reverse();return r;};

Анонимный метод, который возвращает список целых чисел после выполнения операций постановки в очередь и снятия с очереди. Отрицательные целые числа используются для удаления элементов из очереди.

Полная программа с методикой ungolfed и тестовыми примерами:

using System;
using System.Collections.Generic;

public class Program
{
    static void PrintList(List<int> list)
    {
        var s = "{";
        foreach (int element in list)
            s += element + ", ";
        if (s.Length > 1)
            s += "\b\b";
        s += "}";
        Console.WriteLine(s);
    }

    public static void Main()
    {
        Func<List<int>, List<int>> f =
        l =>
        {
            var r = new List<int>();
            foreach (var n in l)
                if (n < 0)
                    try
                    {
                        r.RemoveAt(0);
                    }
                    catch
                    { }
                else
                    r.Add(n);
            r.Reverse();
            return r;
        };

        // test cases:
        var list = new List<int>(new[]{1, -1, 2, -1, 3, -1});   // {}
        PrintList(f(list));

        list = new List<int>(new[]{1, 2, -1});  // {2}
        PrintList(f(list));

        list = new List<int>(new[]{1, 2, 3});   // {3, 2, 1}
        PrintList(f(list));

        list = new List<int>(new[]{1, 2, -1, -1, -1, 3});   // {3}
        PrintList(f(list));

        list = new List<int>(new[]{1, 2, -1, 3, -1, 4});    // {4, 3}
        PrintList(f(list));
    }
}

Скала, 97 байт

type S=Seq[_];def f(a:S,b:S):S=a match{case h::t=>f(t,if(h==0)b dropRight 1 else h+:b);case _=>b}

В качестве входных данных fпринимает список с 0элементом «dequeue». Он использует хвостовую рекурсию со вторым параметром ( b), выступая в качестве аккумулятора. Первоначально, bпусто Seq( Nil).

Пояснения:

type S=Seq[_]                               // defines a type alias (save 1 byte since Seq[_] is used 3 times)
def f(a: S, b: S): S = {                    // a is the initial list, b is an accumulator
    a match {                           
        case h::t =>                        // if a is non-empty
            f(t,                            // recursive call to f with 1st parameter as the tail
                if (h==0) b dropRight 1     // if h == 0 (dequeue) then remove last element of b,
                else h+:b                   // otherwise, just add h at the beginning of b in recursive call
            )
        case _ => b                         // when the list is empty, return b (final result)
    }
}

Примечание: b dropRight 1 используется вместо , b.tailчтобы избежать исключения: tail of empty list.

Тестовые случаи:

f(Seq(45, 0, 0, 37, 20, 0, 97, 0, 85), Nil)     // List(85, 97)
f(Seq(1, 0, 2, 0, 3, 0), Nil)                   // List()
f(Seq(1, 2, 0), Nil)                            // List(2)
f(Seq(1, 2, 3), Nil)                            // List(3, 2, 1)
f(Seq(1, 2, 0, 0, 0, 3), Nil)                   // List(3)
f(Seq(1, 2, 0, 3, 0, 4), Nil)                   // List(4, 3)

fможет также работать с другими типами ( String, char..., даже гетерогенный список этих типов!):

f(Seq(false, '!', "world", 0, "Hello"), Nil)    // List(Hello, world, !)

REXX, 115 байт

arg n
do while n>''
  parse var n m n
  if m=X then pull
  else queue m
  end
o=
do while queued()>0
  pull a
  o=a o
  end
say o

Принимает разделенную пробелами строку, печатает разделенную пробелами строку

C ++, 122 119 байт

#import<list>
void f(std::list<int>o,std::list<int>&q){for(int i:o)if(i)q.push_front(i);else if(q.size())q.pop_back();}

0 указывает на очередь.

Попробуйте онлайн!

Swift 3, 70 байт

Предполагая, что у нас есть массив Ints, как let x = [1, 2,-1,3,-1,4]

print(x.reduce([].prefix(0)){(a,i)in return i>0 ?[i]+a:a.dropLast(1)})

Обратите внимание, что [].prefix(0)это хитрый способ получить пустой ArraySlice