Очередь, содержащая одно целое число

Question

У нас есть очередь, которая содержит только одно целое число, скажем, a.Теперь это a может принимать различные значения, т.е. изначально a = 2. Когда я добавляю еще одно число в очередь, оно становится 24. Если я добавлю еще одно целое число, скажем, 5, оно станет 245. Когда я удаляю элемент из очереди, оно становится 24, затем 2, а затем пусто и т. д.

У нас может быть случай, когда есть начальные и конечные 0, т. е. a = 000123. Но так как a является целым числом, внутренне оно будет представлено как 123. Так какМожем ли мы выполнить операцию по удалению элемента из этого элемента очереди и при этом убедиться, что a представлено так, как ожидается.то есть, когда 3,2,1 удалены, у нас будет 0 как внутренне, но мы хотим убедиться, что мы не потеряем след из 3 ведущих нулей.

Теперь предостережение состоит в том, что внутренне a будет представлен как123. Но нам разрешено использовать дополнительную переменную для отслеживания ведущих нулей.

Мое решение состояло в том, чтобы использовать целое число для отслеживания длины a (в виде строки) и выполнения операций над преобразованным таким образомнанизывать).Так, например, если a = 00123 и len (a) = 5, то у нас 2 ведущих нуля.Поэтому, когда a.remove () вызывается для 3,2,1, мы знаем, что у нас на самом деле 2 ведущих нуля.

Правильно ли мое решение?И есть ли лучший способ?

Спасибо!

Answer 1

Вам необходимо учитывать несколько групп нулей. Например "001001".

class DigitStack(object):
    def __init__(self):
        self.value = 0
        self.numZeros = 0
        self.count = 0

    def push(self,digit):
        "Add a digit to the stack"
        if digit == 0:
            # Skip zeros; Just count them.
            self.numZeros += 1
        else:
            # Push back any zeros we skipped earlier.
            while self.numZeros > 0:
              self.value *= 10
              self.numZeros -= 1
            self.value = self.value * 10 + digit
        self.count = self.count + 1

    def pop(self):
         "Remove a digit from the stack"
        if self.count == 0:
            raise IndexError("Empty stack")
        elif self.numZeros > 0:
            self.numZeros -= 1
            self.count -= 1
            return 0
        else:
            self.value, digit = divmod(self.value, 10)
            self.count -= 1
            return digit

   def dropZeros(self):
        "Drop any zeros we have accumulated"
       self.numZeros = 0

   def __len__(self):
       "Number of digits in the stack"
       return self.count

С этим мы можем добраться до основного алгоритма:

def dropLeadingZeros(stack):
     "Remove any leading zeros, at the bottom of the stack"
     # Another stack, to hold the values we
     # pop from the main stack.
    accum = DigitStack()
    while stack:  # not empty
        digit = stack.pop()
        accum.push(digit)
   # Drop the last zeros.
   accum.dropZeros()
   # Put it all back, except for the leading zeros.
   while accum:  # not empty
       digit = accum.pop()
       stack.push(digit)

Answer 2

Что ж, похоже, вы описываете стек, а не очередь (вы добавляете 2, затем 4, затем 5; затем удаляете 5, затем 4, затем 2).

Я бы сказал, что лучшим решением будет использование реального стека или очереди, предпочтительно встроенной в стандартную библиотеку любого языка, который вы используете. Что произойдет, если вам нужно добавить больше цифр, чем может быть представлено int или long вашего языка?

Однако, если у вас есть (странные) ограничения, которые означают, что вам нужно реализовать его как одно целое число, ваше решение звучит нормально для меня.

Обратите внимание, что вам не нужно ничего преобразовывать в строку.

Вот некоторый псевдо / C # код, который я придумал:

class MyStack {
   int leadingZeros = 0;
   int value = 0;
   public void Add(int i) {
      if (value == 0 && i == 0) {
         leadingZeros++;
      } else {
         value = value*10 + i
      }
   }
   public int Remove() {
      if (value==0) {
         leadingZeros--;
         return 0;
      } else { 
         int i = value % 10;
         value /= 10;
         return i;
      }
   }
}

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