Problem of the Day -- 2 Stacks 1 Queue

2 Stacks 1 Queue

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.

Permalink: http://problemotd.com/problem/2-stacks-1-queue/

Comments:

Kevin Benton - 10 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 - 10 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 - 10 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 - 10 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 - 9 years, 12 months 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

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

2 Stacks 1 Queue

Comments:

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