10000 Revisions in README.markdown · matsoftware/swift-algorithm-club@499bd86 · GitHub
[go: up one dir, main page]

Skip to content

Commit 499bd86

Browse files
author
Parva9eh
authored
Revisions in README.markdown
I have revised your document to be more concise. Some words and phrases are removed or replaced due to redundancy.
1 parent 36f374e commit 499bd86

File tree

1 file changed

+26
-26
lines changed

1 file changed

+26
-26
lines changed

Queue/README.markdown

Lines changed: 26 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -2,11 +2,11 @@
22

33
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!
44

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.
66

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.)
88

9-
For example, let's enqueue a number:
9+
Here is an example to enqueue a number:
1010

1111
```swift
1212
queue.enqueue(10)
@@ -38,11 +38,11 @@ queue.dequeue()
3838

3939
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.
4040

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.
4242
4343
## The code
4444

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:
4646

4747
```swift
4848
public struct Queue<T> {
@@ -74,11 +74,11 @@ public struct Queue<T> {
7474
}
7575
```
7676

77-
This queue works just fine but it is not optimal.
77+
This queue works well, but it is not optimal.
7878

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.
8080

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:
8282

8383
```swift
8484
var queue = Queue<String>()
@@ -95,13 +95,13 @@ where `xxx` is memory that is reserved but not filled in yet. Adding a new eleme
9595

9696
[ "Ada", "Steve", "Tim", "Grace", xxx, xxx ]
9797

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.
9999

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.
101101

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".
103103

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.
105105

106106
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"`:
107107

@@ -112,27 +112,27 @@ In our example, dequeuing the first element `"Ada"` copies `"Steve"` in the plac
112112
/ / /
113113
after [ "Steve", "Tim", "Grace", xxx, xxx, xxx ]
114114

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...
116116

117117
## A more efficient queue
118118

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.
120120

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:
122122

123123
[ xxx, "Steve", "Tim", "Grace", xxx, xxx ]
124124

125125
After dequeuing `"Steve"`, the array is:
126126

127127
[ xxx, xxx, "Tim", "Grace", xxx, xxx ]
128128

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:
130130

131131
[ "Tim", "Grace", xxx, xxx, xxx, xxx ]
132132

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.
134134

135-
Here is how you could implement this version of `Queue`:
135+
Here is how you can implement this version of `Queue`:
136136

137137
```swift
138138
public struct Queue<T> {
@@ -176,9 +176,9 @@ public struct Queue<T> {
176176
}
177177
```
178178

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.
180180

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.
182182

183183
We go from this:
184184

@@ -190,9 +190,9 @@ to this:
190190
[ xxx, "Steve", "Tim", "Grace", xxx, xxx ]
191191
head
192192

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.
194194

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:
196196

197197
```swift
198198
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
202202
}
203203
```
204204

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.
206206

207207
> **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.
208208
209-
To test this in a playground, do:
209+
To test this in a playground, do the following:
210210

211211
```swift
212212
var q = Queue<String>()
@@ -251,11 +251,11 @@ q.array // [{Some "Grace"}]
251251
q.count // 1
252252
```
253253

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.
255255

256256
## See also
257257

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/).
259259

260260
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.
261261

0 commit comments

Comments
 (0)
0