A standard queue (FIFO - First In First Out) implemented in Swift. Supports simultaneous adding and removing, but only one item can be added at a time, and only one item can be removed at a time. Using the "Two-Lock Concurrent Queue Algorithm" from http://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html#tlq, without the locks.

Queue.swift

//
//  Queue.swift
//  NTBSwift
//
//  Created by Kåre Morstøl on 11/07/14.
//
//  Using the "Two-Lock Concurrent Queue Algorithm" from http://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html#tlq, without the locks.


// should be an inner class of Queue, but inner classes and generics crash the compiler, SourceKit (repeatedly) and occasionally XCode. 
class _QueueItem<T> {
	let value: T!
	var next: _QueueItem?	
	
	init(_ newvalue: T?) {
		self.value = newvalue
	}
}

///
/// A standard queue (FIFO - First In First Out). Supports simultaneous adding and removing, but only one item can be added at a time, and only one item can be removed at a time.
///
public class Queue<T> {
	
	typealias Element = T
	
	var _front: _QueueItem<Element>
	var _back: _QueueItem<Element>
	
	public init () {
		// Insert dummy item. Will disappear when the first item is added.
		_back = _QueueItem(nil)
		_front = _back
	}
	
	/// Add a new item to the back of the queue.
	public func enqueue (value: Element) {
		_back.next = _QueueItem(value)
		_back = _back.next!
	}
	
	/// Return and remove the item at the front of the queue.
	public func dequeue () -> Element? {
		if let newhead = _front.next {
			_front = newhead
			return newhead.value
		} else {
			return nil
		}
	}
	
	public func isEmpty() -> Bool {
		return _front === _back
	}
}

QueueTests.swift

//
//  QueueTests.swift
//
//  Created by Kåre Morstøl on 11/07/14.
//  Copyright (c) 2014 NotTooBad Software. All rights reserved.
//

import XCTest 
import NTBSwift

class QueueTests: XCTestCase {
    
    func testAdd1ToQueue() {
		let sut = Queue<String>()
		sut.enqueue("1")
    }

	func testAddSeveralToQueue() {
		let sut = Queue<String>()
		XCTAssert(sut.isEmpty())
		sut.enqueue("1")
		sut.enqueue("1")
		XCTAssertFalse(sut.isEmpty())
		sut.enqueue("1")
		sut.enqueue("1")
		sut.enqueue("1")
	}
	
	func testRemoveOne() {
		let sut = Queue<String>()
		sut.enqueue("1")
		sut.enqueue("")
		sut.enqueue("")
		sut.enqueue("")
		let thefirstone = sut.dequeue()
		
		XCTAssertNotNil(thefirstone)
		XCTAssertEqual(thefirstone!, "1")
	}
	
	func testRemoveAll() {
		let sut = Queue<String>()
		sut.enqueue("1")
		sut.enqueue("2")
		sut.enqueue("3")
		sut.enqueue("4")

		XCTAssertEqual(sut.dequeue()!, "1")
		XCTAssertEqual(sut.dequeue()!, "2")
		XCTAssertEqual(sut.dequeue()!, "3")
		XCTAssertEqual(sut.dequeue()!, "4")
		XCTAssert(sut.isEmpty())
		XCTAssertNil(sut.dequeue())
		XCTAssertNil(sut.dequeue())
		XCTAssert(sut.isEmpty())
	}
	
	func testGenerics() {
		let sut = Queue<Int>()
		sut.enqueue(1)
		sut.enqueue(2)
		sut.enqueue(3)
		sut.enqueue(4)
		
		XCTAssertEqual(sut.dequeue()!, 1)
		XCTAssertEqual(sut.dequeue()!, 2)
		XCTAssertEqual(sut.dequeue()!, 3)
		XCTAssertEqual(sut.dequeue()!, 4)
	}
	
	func  testAddNil() {
		let sut = Queue<Int?>()
		sut.enqueue(nil)
		XCTAssertNil(sut.dequeue()?)
		
		sut.enqueue(2)
		sut.enqueue(nil)
		sut.enqueue(4)
		
		XCTAssertEqual(sut.dequeue()!!, 2)
		XCTAssertNil(sut.dequeue()?)
		XCTAssertEqual(sut.dequeue()!!, 4)
	}

	func testAddAfterEmpty() {
		let sut = Queue<String>()
		
		sut.enqueue("1")
		XCTAssertEqual(sut.dequeue()!, "1")
		XCTAssertNil(sut.dequeue())
		
		sut.enqueue("1")
		sut.enqueue("2")
		XCTAssertEqual(sut.dequeue()!, "1")
		XCTAssertEqual(sut.dequeue()!, "2")
		XCTAssert(sut.isEmpty())
		XCTAssertNil(sut.dequeue())
	}
	
	func testAddAndRemoveChaotically() {
		let sut = Queue<String>()
		
		sut.enqueue("1")
		XCTAssertFalse(sut.isEmpty())
		XCTAssertEqual(sut.dequeue()!, "1")
		XCTAssert(sut.isEmpty())
		XCTAssertNil(sut.dequeue())

		sut.enqueue("1")
		sut.enqueue("2")
		XCTAssertEqual(sut.dequeue()!, "1")
		XCTAssertEqual(sut.dequeue()!, "2")
		XCTAssert(sut.isEmpty())
		XCTAssertNil(sut.dequeue())

		sut.enqueue("1")
		sut.enqueue("2")
		XCTAssertEqual(sut.dequeue()!, "1")
		sut.enqueue("3")
		sut.enqueue("4")
		XCTAssertEqual(sut.dequeue()!, "2")
		XCTAssertEqual(sut.dequeue()!, "3")
		XCTAssertFalse(sut.isEmpty())
		XCTAssertEqual(sut.dequeue()!, "4")
		XCTAssertNil(sut.dequeue())
		XCTAssertNil(sut.dequeue())
	}

	func testConcurrency() {
		let sut = Queue<Int>()
		let numberofiterations = 2_000_00

		let addingexpectation = expectationWithDescription("adding completed")
		let addingqueue = dispatch_queue_create( "adding", DISPATCH_QUEUE_SERIAL)
		dispatch_async(addingqueue)  {
			for i in  1...numberofiterations {
				sut.enqueue(i)
			}
			addingexpectation.fulfill()
		}
		
		let deletingexpectation = expectationWithDescription("deleting completed")
		let deletingqueue = dispatch_queue_create( "deleting", DISPATCH_QUEUE_SERIAL)
		dispatch_async(deletingqueue)  {
			for (var i=1; i <= numberofiterations; 0) {
				if let result = sut.dequeue() {
					XCTAssertEqual(result, i)
					i++
				} else {
					println(" pausing deleting for one second")
					sleep(CUnsignedInt(1))
				}
			}
			deletingexpectation.fulfill()
		}
		
		waitForExpectationsWithTimeout( 600, handler:  nil)
	} 
}

Thank you so much.

Thanks for this. Would you consider adding a comment to the file saying what license(s) it is offered under?

testAddNil() causes problems in Swift 2.0, fyi.

It seems like this queue leaks one Element size of memory? Since an empty queue always hold on one element.

@honghaoz when empty it holds one _QueueItem with 'nil' for value. This is to avoid dealing with empty queue every time you add or remove something.

This is released under an MIT License

Where are the locks? The first solution in that MIT article uses CAS which is an atomic operation and what is your workaround for that CAS operation?

`testConcurrency` tests simultaneous adding and removing. But as it says in the description: “ Supports simultaneous adding and removing, but only one item can be added at a time, and only one item can be removed at a time”.

…

31. jul. 2020 kl. 20:43 skrev Sébastien Stormacq ***@***.***>: ***@***.*** commented on this gist. unless I missed something, this solution is not thread safe. What if one thread enqueue while another thread dequeue ? — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub, or unsubscribe.