Queue containing a single integer

We have a queue which contains only a single integer say a. 开发者_Go百科Now this a can take various values i.e. initially a = 2. When I add another number to the queue, it becomes 24. If I add another integer say 5, it becomes 245. When I remove an element from the queue, it becomes 24, then 2 and then empty and so on.

We can have a case where there are leading and trailing 0's i.e. a = 000123. But as a is an integer, internally it will be represented as 123. So how can we perform the operation to remove an element from this queue element and still make sure that a is represented as expected. i.e. when 3,2,1 are removed we will have 0 as internally but we want to make sure that we do not lose track of the 3 leading 0s.

Now the caveat is that internally a will be represented as 123. But we are allowed to use extra variable to keep track of leading zeros.

My solution was to use an integer to keep track of length of a (as a string) and perform the operations on a thus converted to string). So if e.g. a = 00123 and len(a) = 5, then we have 2 leading 0s. So when a.remove() is called to 3,2,1, we know that we actually have 2 leading 0s in place.

Is my solution correct? And is there a better way?

Thanks!

You need to consider multiple groups of zeros. For example "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

With this we can get to the main algorithm:

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)

Well, you seem to be describing a stack rather than a queue (you add 2, then 4 then 5; then remove 5 then 4 then 2).

I would say the best solution would be to use a real stack or queue, preferably one built into the standard library of whichever language you are using. What happens if you need to add more digits than can be represented by your language's int or long?

However, assuming you have (strange) constraints which mean you need to implement it as a single integer, your solution sounds ok to me.

Note that you don't need to actually convert anything to a string.

Here's some pseudo/C# code I came up with:

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;
      }
   }
}

Note that I am assuming you will add one-digit numbers only, and I've left out any error handling.