Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 53
Good morning! Here's your coding interview problem for today.

This problem was asked by Apple.

Implement a queue using two stacks. Recall that a queue is a FIFO (first-in, first-out) data structure with the following methods: enqueue, which inserts an element into the queue, and dequeue, which removes it.

Pull request:
Day53
Resolves #114 .

Patch:
diff --git a/README.md b/README.md
index 6177998..bb37274 100644
--- a/README.md
+++ b/README.md
@@ -62,3 +62,4 @@ problems from
 * [Day 47](https://github.com/vaskoz/dailycodingproblem-go/issues/105)
 * [Day 49](https://github.com/vaskoz/dailycodingproblem-go/issues/107)
 * [Day 50](https://github.com/vaskoz/dailycodingproblem-go/issues/110)
+* [Day 53](https://github.com/vaskoz/dailycodingproblem-go/issues/114)
diff --git a/day53/problem.go b/day53/problem.go
new file mode 100644
index 0000000..32c13ef
--- /dev/null
+++ b/day53/problem.go
@@ -0,0 +1,65 @@
+package day53
+
+import "errors"
+
+var errEmpty = errors.New("empty")
+
+// ErrEmpty is the error returned for an empty data structure.
+func ErrEmpty() error {
+	return errEmpty
+}
+
+// Stack represents a LIFO data structure.
+type Stack interface {
+	Push(val interface{})
+	Pop() (interface{}, error)
+}
+
+// Queue represents a FIFO data structure.
+type Queue interface {
+	Enqueue(item interface{})
+	Dequeue() (interface{}, error)
+}
+
+type stack struct {
+	values []interface{}
+}
+
+func (s *stack) Push(val interface{}) {
+	s.values = append(s.values, val)
+}
+
+func (s *stack) Pop() (interface{}, error) {
+	if len(s.values) == 0 {
+		return nil, ErrEmpty()
+	}
+	var x interface{}
+	x, s.values = s.values[len(s.values)-1], s.values[:len(s.values)-1]
+	return x, nil
+}
+
+type twoStacksQueue struct {
+	enqueue, dequeue *stack
+}
+
+func (tsq twoStacksQueue) Enqueue(item interface{}) {
+	tsq.enqueue.Push(item)
+}
+
+func (tsq twoStacksQueue) Dequeue() (interface{}, error) {
+	if val, err := tsq.dequeue.Pop(); err == nil {
+		return val, nil
+	}
+	for val, err := tsq.enqueue.Pop(); err == nil; val, err = tsq.enqueue.Pop() {
+		tsq.dequeue.Push(val)
+	}
+	if val, err := tsq.dequeue.Pop(); err == nil {
+		return val, nil
+	}
+	return nil, ErrEmpty()
+}
+
+// NewQueue returns a queue. FIFO.
+func NewQueue() Queue {
+	return &twoStacksQueue{&stack{}, &stack{}}
+}


Test patch:
diff --git a/day53/problem_test.go b/day53/problem_test.go
new file mode 100644
index 0000000..2805b79
--- /dev/null
+++ b/day53/problem_test.go
@@ -0,0 +1,43 @@
+package day53
+
+import "testing"
+
+var testcases = []struct {
+	inserts []interface{}
+}{
+	{[]interface{}{"foo", "bar", 1, 3, 5, 6}},
+}
+
+func TestQueue(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		q := NewQueue()
+		for _, v := range tc.inserts {
+			q.Enqueue(v)
+		}
+		for _, v := range tc.inserts {
+			if res, err := q.Dequeue(); err != nil {
+				t.Errorf("Expected no errors while dequeuing")
+			} else if res != v {
+				t.Errorf("Expected results in FIFO order. Expected %v, got %v", v, res)
+			}
+		}
+		if _, err := q.Dequeue(); err == nil {
+			t.Errorf("Dequeue on empty queue should return an error")
+		}
+	}
+}
+
+func BenchmarkQueue(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			q := NewQueue()
+			for _, v := range tc.inserts {
+				q.Enqueue(v)
+			}
+			for range tc.inserts {
+				q.Dequeue()
+			}
+		}
+	}
+}