Problem of the Day
A new programming or logic puzzle every Mon-Fri

Let's try and take a different spin on yesterday's problem. Today's goal will be to implement a stack. Then using two instances of the stack you'll want to mimic the functionality of a queue. Thus your queue will have an enqueue and dequeue method but those methods will only use the push and pop functionality of your stacks.

Comments:

• Kevin Benton - 11 years ago

  class Stack(object):
  
      def __init__(self):
          self._store = []
  
      def push(self, x):
          return self._store.append(x)
  
      def pop(self):
          return self._store.pop()
  
  
  class Queue(object):
  
      def __init__(self):
          self.instack = Stack()
          self.outstack = Stack()
  
      def __str__(self):
          return str(self.instack._store)
  
      def enqueue(self, x):
          self.instack.push(x)
          return self
  
      def dequeue(self):
          # pour one stack into the other
          while True:
              try:
                  self.outstack.push(self.instack.pop())
              except IndexError:
                  break
          # take the top
          top = self.outstack.pop()
          # pour it back and return the top
          while True:
              try:
                  self.instack.push(self.outstack.pop())
              except IndexError:
                  return top
  
  
  myqueue = Queue()
  
  print myqueue.enqueue(5)
  print myqueue.enqueue(6)
  print myqueue.enqueue(7)
  print myqueue.enqueue(8)
  print myqueue.dequeue()
  print myqueue.dequeue()
  

  reply permalink

• Adam - 11 years ago

  This one's a bit more efficient, it doesn't need to pour the stacks into each other on each deque:

  class Queue():
      def __init__(self):
          self.instack = []
          self.outstack = []
  
      def enqueue(self, item):
          self.instack.append(item)
  
      def dequeue(self):
          # First pop from the out stack if there's anything in there
          if len(self.outstack) > 0:
              return self.outstack.pop()
  
          else:
              # When it's empty, refill it from the in stack
              while True:
                  try:
                      self.outstack.append(self.instack.pop())
                  except IndexError:
                      break
          return self.outstack.pop()
  

  reply permalink

• Anonymous - 11 years ago

  "c suxx 2: eletric boogaloo"

  I'm not going to try to solve this problems with C anymore.

  #include <stdlib.h>
  #include <stdio.h>
  #include <stdbool.h>
  
  #define STACK_OF_TYPE(type) \
  typedef struct __Node_##type { \
    struct __Node_##type *prev; \
    type value; \
  } Node_##type; \
  typedef struct __Stack_##type { \
    Node_##type* top; \
    size_t size; \
  } Stack_##type; \
  Stack_##type* stack_##type##_create() { \
    Stack_##type* result = malloc(sizeof(Stack_##type)); \
    result->top = NULL; \
    result->size = 0; \
    return result; \
  } \
  Node_##type* node_##type##_create(type value) { \
    Node_##type* result = malloc(sizeof(Node_##type)); \
    result->prev = NULL; \
    result->value = value; \
    return result; \
  } \
  void stack_##type##_push(Stack_##type* deque, type value) { \
    Node_##type* pushed = node_##type##_create(value); \
    if(deque->top == NULL) { \
      deque->top = pushed; \
    } else { \
      pushed->prev = deque->top; \
      deque->top = pushed; \
    } \
    deque->size++; \
  }  \
  typedef struct __Stack_##type##_result { \
    type value; \
    bool error; \
  } Stack_##type##_result; \
  Stack_##type##_result stack_##type##_pop(Stack_##type* deque) { \
    if(deque->top == NULL) { \
      Stack_##type##_result result = { .error = true }; \
      return result; \
    } else { \
      Node_##type* popped = deque->top; \
      deque->top = popped->prev; \
      type value = popped->value; \
      free(popped); \
      deque->size--; \
      Stack_##type##_result result = { value, true }; \
      return result; \
    } \
  } \
  type* stack_##type##_array(Stack_##type* deque) { \
    type* result = malloc(sizeof(type) * deque->size); \
    int count = 0; \
    for(Node_##type* n = deque->top; n != NULL; n = n->prev) { \
      result[count++] = n->value; \
    } \
    return result; \
  }
  
  #define QUEUE_OF_TYPE(type) \
  typedef struct __Queue_##type { \
    Stack_##type* temp; \
    Stack_##type* real; \
    size_t size; \
  } Queue_##type; \
  Queue_##type* queue_##type##_create() { \
    Queue_##type *result = malloc(sizeof(Queue_##type)); \
    result->temp = stack_##type##_create(); \
    result->real = stack_##type##_create(); \
    result->size = 0; \
    return result; \
  } \
  void queue_##type##_enqueue(Queue_##type* queue, int value) { \
    stack_##type##_push(queue->real, value); \
    queue->size++; \
  } \
  typedef struct { \
    bool error; \
    int value; \
  } Queue_##type_result; \
  Queue_##type_result queue_##type##_dequeue(Queue_##type* queue) { \
    if(queue->size == 0) { \
      Queue_##type_result result = { .error = true }; \
      return result; \
    } \
      while(queue->real->size > 0) { \
      stack_##type##_push(queue->temp, stack_##type##_pop(queue->real).value); \
    } \
    Queue_##type_result result = { stack_##type##_pop(queue->temp).value, false }; \
    while(queue->temp->size > 0) { \
      stack_##type##_push(queue->real, stack_##type##_pop(queue->temp).value); \
    } \
    queue->size--; \
    return result; \
  } \
  type* queue_##type##_array(Queue_##type* queue) { \
    return stack_##type##_array(queue->real); \
  }
  
  STACK_OF_TYPE(char)
  
  QUEUE_OF_TYPE(char)
  
  void print_queue_char(Queue_char* queue) {
    char* array = queue_char_array(queue);
    if(queue->size > 0) for(int i = 0; i < queue->size; i++) {
      printf("%c", array[i]);
    }
    printf("\n");
    free(array);
  }
  
  int main(int argc, char** argv) {
    Queue_char* queue = queue_char_create();
    queue_char_enqueue(queue, 'a');
    queue_char_enqueue(queue, 'b');
    queue_char_enqueue(queue, 'c');
  
    print_queue_char(queue);
  
    queue_char_dequeue(queue);
  
    print_queue_char(queue);
  
    return 0;
  }
  

  reply permalink

• Adam - 11 years ago

  Learning the state monad in Haskell:

  import Control.Monad.Trans.State
  
  newtype Stack a = Stack [a]
      deriving (Show)
  
  newtype Queue a = Queue (Stack a, Stack a)
      deriving (Show)
  
  newQueue = Queue (Stack [], Stack [])
  
  pop :: State (Stack a) (Maybe a)
  pop = state $ \(Stack xss) -> case xss of
      [] -> (Nothing, Stack xss)
      x:xs -> (Just x, Stack xs)
  
  push :: a -> State (Stack a) ()
  push x = modify $ \(Stack xs) -> Stack (x:xs)
  
  dequeue :: State (Queue a) (Maybe a)
  dequeue = state $ \q@(Queue (aStack, bStack)) ->
      case (runState pop bStack) of
          (Just x, newB)   -> (Just x, Queue (aStack, newB))
          (Nothing, origB) -> case (runState pop aStack) of
              (Just x, newA)   -> runState dequeue (transfer q)
              (Nothing, origA) -> (Nothing, q)
  
  enqueue :: a -> State (Queue a) ()
  enqueue x = modify $ \(Queue (aStack, bStack)) ->
      let newA = execState (push x) aStack
      in Queue (newA, bStack)
  
  -- transfer from in stack (a) to out stack (b)
  transfer :: Queue a -> Queue a
  transfer (Queue (aStack, bStack)) =
      case (runState pop aStack) of
          (Nothing, origA) -> Queue (origA, bStack)
          (Just x, newA) -> transfer $ Queue (newA, newB)
              where newB = execState (push x) bStack
  

  reply permalink

• Bill Bejeck - 11 years ago

  public class TwoStacks {

  public static void main(String[] args) {
      QueueImpl queue = new QueueImpl();
      System.out.println("Adding 1,2,3 in order");
      queue.enqueue("1");
      queue.enqueue("2");
      queue.enqueue("3");
  
      System.out.println("Now getting from Queue expected order 1,2,3");
      System.out.println(queue.dequeue());
      System.out.println(queue.dequeue());
      System.out.println(queue.dequeue());
  
  }
  
  private static class QueueImpl implements Queue<String> {
  
      private Stack<String> s1 = new Stack<>();
      private Stack<String> s2 = new Stack<>();
  
      private Stack<String> liveStack;
      private Stack<String> auxStack;
  
      private QueueImpl() {
          liveStack = s1;
          auxStack = s2;
      }
  
      @Override
      public void enqueue(String item) {
            auxStack.push(item);
  
      }
  
      @Override
      public String dequeue() {
         while(!auxStack.isEmpty()){
             liveStack.push(auxStack.pop());
         }
        return  liveStack.pop();
      }
  
  
  }
  
  
  private static interface Queue<T> {
       void enqueue(T item);
       T dequeue();
  }
  

  }

  reply permalink