Data Structures & Algorithms in Swift 路 Queue | raywenderlich.com

馃帗 Courses & Articles
1
This is a companion discussion topic for the original entry at https://www.raywenderlich.com/977854-data-structures-algorithms-in-swift/lessons/5
2

Hi Catie,
what is the complexity of copying the reversed enqueueStack to the dequeueStack?
Does it affect the overall complexity of using two stacks compared to the array option during dequeuing?

Regards
Simone

3

@catie @jessycatterwaul @jcatterwaul Can you please help with this when you get a chance? Thank you - much appreciated! :]

4

Hi Simone!

Reversing the enqueue stack is an O(n) operation, but because it only happens when the dequeue stack is empty, it doesn鈥檛 affect the overall complexity. The time complexity of dequeueing with two stacks still averages out to O(1), whereas the array implementation will always be O(n).

5

Hi @catie

How the peek() is going to work for queue using the stack.

Thanks

6

Hi! I recommend you check out the video around 7:00 again. To read that code in more of a sentence form:

If the dequeue stack is NOT empty, return the last item in the dequeue stack. Otherwise, return the first item in the enqueue stack.

7

I thought it was standard for time complexity to be considered by worst case. Thus, worst case is O(n) for dequeue

8

Looks like you are using array for both QueueStack & QueueArray. Stack type would have imposed to use push & pop methods. Is that mistake or did I understood wrongly?

9

@catie @jessycatterwaul @jcatterwaul Do you have any feedback about this? Thank you - much appreciated! :]

10

Hi! Yes, using a Stack type could impose those restrictions, we just would have needed to add some functionality to that type to use it here. To keep things simpler in this episode, for QueueStack, we made the enqueue and dequeue arrays private, and treated them as if they were stacks within QueueStack.