You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Copy file name to clipboardExpand all lines: Queue/README.markdown
+26-26Lines changed: 26 additions & 26 deletions
Original file line number
Diff line number
Diff line change
@@ -2,11 +2,11 @@
2
2
3
3
A queue is a list where you can only insert new items at the back and remove items from the front. This ensures that the first item you enqueue is also the first item you dequeue. First come, first serve!
4
4
5
-
Why would you need this? Well, in many algorithms you want to add objects to a temporary list at some point and then pull them off this list again at a later time. Often the order in which you add and remove these objects matters.
5
+
Why would you need this? Well, in many algorithms you want to add objects to a temporary list and pull them off this list later. Often the order in which you add and remove these objects matters.
6
6
7
-
A queue gives you a FIFO or first-in, first-out order. The element you inserted first is also the first one to come out again. It's only fair! (A very similar data structure, the [stack](../Stack/), is LIFO or last-in first-out.)
7
+
A queue gives you a FIFO or first-in, first-out order. The element you inserted first is the first one to come out. It is only fair! (A similar data structure, the [stack](../Stack/), is LIFO or last-in first-out.)
8
8
9
-
For example, let's enqueue a number:
9
+
Here is an example to enqueue a number:
10
10
11
11
```swift
12
12
queue.enqueue(10)
@@ -38,11 +38,11 @@ queue.dequeue()
38
38
39
39
This returns `3`, the next dequeue returns `57`, and so on. If the queue is empty, dequeuing returns `nil` or in some implementations it gives an error message.
40
40
41
-
> **Note:** A queue is not always the best choice. If the order in which the items are added and removed from the list isn't important, you might as well use a [stack](../Stack/) instead of a queue. Stacks are simpler and faster.
41
+
> **Note:** A queue is not always the best choice. If the order in which the items are added and removed from the list is not important, you can use a [stack](../Stack/) instead of a queue. Stacks are simpler and faster.
42
42
43
43
## The code
44
44
45
-
Here is a very simplistic implementation of a queue in Swift. It's just a wrapper around an array that lets you enqueue, dequeue, and peek at the front-most item:
45
+
Here is a simplistic implementation of a queue in Swift. It is a wrapper around an array to enqueue, dequeue, and peek at the front-most item:
46
46
47
47
```swift
48
48
publicstructQueue<T> {
@@ -74,11 +74,11 @@ public struct Queue<T> {
74
74
}
75
75
```
76
76
77
-
This queue works just fine but it is not optimal.
77
+
This queue works well, but it is not optimal.
78
78
79
-
Enqueuing is an **O(1)** operation because adding to the end of an array always takes the same amount of time, regardless of the size of the array. So that's great.
79
+
Enqueuing is an **O(1)** operation because adding to the end of an array always takes the same amount of time regardless of the size of the array.
80
80
81
-
You might be wondering why appending items to an array is **O(1)**, or a constant-time operation. That is so because an array in Swift always has some empty space at the end. If we do the following:
81
+
You might be wondering why appending items to an array is **O(1)** or a constant-time operation. That is because an array in Swift always has some empty space at the end. If we do the following:
82
82
83
83
```swift
84
84
var queue = Queue<String>()
@@ -95,13 +95,13 @@ where `xxx` is memory that is reserved but not filled in yet. Adding a new eleme
95
95
96
96
[ "Ada", "Steve", "Tim", "Grace", xxx, xxx ]
97
97
98
-
This is simply matter of copying memory from one place to another, a constant-time operation.
98
+
This results by copying memory from one place to another which is a constant-time operation.
99
99
100
-
Of course, there are only a limited number of such unused spots at the end of the array. When the last `xxx` gets used and you want to add another item, the array needs to resize to make more room.
100
+
There are only a limited number of unused spots at the end of the array. When the last `xxx` gets used, and you want to add another item, the array needs to resize to make more room.
101
101
102
-
Resizing includes allocating new memory and copying all the existing data over to the new array. This is an **O(n)** process, so it's relatively slow. But since it happens only every so often, the time for appending a new element to the end of the array is still **O(1)** on average, or **O(1)** "amortized".
102
+
Resizing includes allocating new memory and copying all the existing data over to the new array. This is an **O(n)** process which is relatively slow. Since it happens occasionally, the time for appending a new element to the end of the array is still **O(1)** on average or **O(1)** "amortized".
103
103
104
-
The story for dequeueing is slightly different. To dequeue we remove the element from the *beginning* of the array, not the end. This is always an **O(n)** operation because it requires all remaining array elements to be shifted in memory.
104
+
The story for dequeueing is different. To dequeue, we remove the element from the *beginning* of the array. This is always an **O(n)** operation because it requires all remaining array elements to be shifted in memory.
105
105
106
106
In our example, dequeuing the first element `"Ada"` copies `"Steve"` in the place of `"Ada"`, `"Tim"` in the place of `"Steve"`, and `"Grace"` in the place of `"Tim"`:
107
107
@@ -112,27 +112,27 @@ In our example, dequeuing the first element `"Ada"` copies `"Steve"` in the plac
112
112
/ / /
113
113
after [ "Steve", "Tim", "Grace", xxx, xxx, xxx ]
114
114
115
-
Moving all these elements in memory is always an **O(n)** operation. So with our simple implementation of a queue, enqueuing is efficient but dequeueing leaves something to be desired...
115
+
Moving all these elements in memory is always an **O(n)** operation. So with our simple implementation of a queue, enqueuing is efficient, but dequeueing leaves something to be desired...
116
116
117
117
## A more efficient queue
118
118
119
-
To make dequeuing more efficient, we can use the same trick of reserving some extra free space, but this time do it at the front of the array. We're going to have to write this code ourselves as the built-in Swift array doesn't support this out of the box.
119
+
To make dequeuing efficient, we can also reserve some extra free space but this time at the front of the array. We must write this code ourselves because the built-in Swift array does not support it.
120
120
121
-
The idea is as follows: whenever we dequeue an item, we don't shift the contents of the array to the front (slow) but mark the item's position in the array as empty (fast). After dequeuing `"Ada"`, the array is:
121
+
The main idea is whenever we dequeue an item, we do not shift the contents of the array to the front (slow) but mark the item's position in the array as empty (fast). After dequeuing `"Ada"`, the array is:
122
122
123
123
[ xxx, "Steve", "Tim", "Grace", xxx, xxx ]
124
124
125
125
After dequeuing `"Steve"`, the array is:
126
126
127
127
[ xxx, xxx, "Tim", "Grace", xxx, xxx ]
128
128
129
-
These empty spots at the front never get reused for anything, so they're wasting space. Every so often you can trim the array by moving the remaining elements to the front again:
129
+
Because these empty spots at the front never get reused, you can periodically trim the array by moving the remaining elements to the front:
130
130
131
131
[ "Tim", "Grace", xxx, xxx, xxx, xxx ]
132
132
133
-
This trimming procedure involves shifting memory so it's an **O(n)** operation. But because it only happens once in a while, dequeuing is now**O(1)** on average.
133
+
This trimming procedure involves shifting memory which is an **O(n)** operation. Because this only happens once in a while, dequeuing is **O(1)** on average.
134
134
135
-
Here is how you could implement this version of `Queue`:
135
+
Here is how you can implement this version of `Queue`:
136
136
137
137
```swift
138
138
publicstructQueue<T> {
@@ -176,9 +176,9 @@ public struct Queue<T> {
176
176
}
177
177
```
178
178
179
-
The array now stores objects of type `T?` instead of just `T` because we need some way to mark array elements as being empty. The `head` variable is the index in the array of the front-most object.
179
+
The array now stores objects of type `T?` instead of just `T` because we need to mark array elements as being empty. The `head` variable is the index in the array of the front-most object.
180
180
181
-
Most of the new functionality sits in `dequeue()`. When we dequeue an item, we first set `array[head]` to `nil` to remove the object from the array. Then we increment `head` because now the next item has become the front one.
181
+
Most of the new functionality sits in `dequeue()`. When we dequeue an item, we first set `array[head]` to `nil` to remove the object from the array. Then, we increment `head` because the next item has become the front one.
182
182
183
183
We go from this:
184
184
@@ -190,9 +190,9 @@ to this:
190
190
[ xxx, "Steve", "Tim", "Grace", xxx, xxx ]
191
191
head
192
192
193
-
It's like some weird supermarket where the people in the checkout lane don't shuffle forward towards the cash register, but the cash register moves up the queue.
193
+
It is like if in a supermarket the people in the checkout lane do not shuffle forward towards the cash register, but the cash register moves up the queue.
194
194
195
-
Of course, if we never remove those empty spots at the front then the array will keep growing as we enqueue and dequeue elements. To periodically trim down the array, we do the following:
195
+
If we never remove those empty spots at the front then the array will keep growing as we enqueue and dequeue elements. To periodically trim down the array, we do the following:
196
196
197
197
```swift
198
198
let percentage =Double(head)/Double(array.count)
@@ -202,11 +202,11 @@ Of course, if we never remove those empty spots at the front then the array will
202
202
}
203
203
```
204
204
205
-
This calculates the percentage of empty spots at the beginning as a ratio of the total array size. If more than 25% of the array is unused, we chop off that wasted space. However, if the array is small we don't want to resize it all the time, so there must be at least 50 elements in the array before we try to trim it.
205
+
This calculates the percentage of empty spots at the beginning as a ratio of the total array size. If more than 25% of the array is unused, we chop off that wasted space. However, if the array is small we do not resize it all the time, so there must be at least 50 elements in the array before we try to trim it.
206
206
207
207
> **Note:** I just pulled these numbers out of thin air -- you may need to tweak them based on the behavior of your app in a production environment.
208
208
209
-
To test this in a playground, do:
209
+
To test this in a playground, do the following:
210
210
211
211
```swift
212
212
var q = Queue<String>()
@@ -251,11 +251,11 @@ q.array // [{Some "Grace"}]
251
251
q.count// 1
252
252
```
253
253
254
-
The `nil` objects at the front have been removed and the array is no longer wasting space. This new version of `Queue` isn't much more complicated than the first one but dequeuing is now also an **O(1)** operation, just because we were a bit smarter about how we used the array.
254
+
The `nil` objects at the front have been removed, and the array is no longer wasting space. This new version of `Queue` is not more complicated than the first one but dequeuing is now also an **O(1)** operation, just because we were aware about how we used the array.
255
255
256
256
## See also
257
257
258
-
There are many other ways to create a queue. Alternative implementations use a [linked list](../Linked%20List/), a [circular buffer](../Ring%20Buffer/), or a [heap](../Heap/).
258
+
There are many ways to create a queue. Alternative implementations use a [linked list](../Linked%20List/), a [circular buffer](../Ring%20Buffer/), or a [heap](../Heap/).
259
259
260
260
Variations on this theme are [deque](../Deque/), a double-ended queue where you can enqueue and dequeue at both ends, and [priority queue](../Priority%20Queue/), a sorted queue where the "most important" item is always at the front.
0 commit comments