Stacks & queues

Stacks and queues are structures that help organize data in a particular order. Their concept is based on the idea that information can be organized similar to how things interact in the real world. For example, a stack of dinner plates can be represented by placing a single plate on a group of existing plates. Similarly, a queue can be easily understood by observing groups of people waiting in a line at a concert or grand opening.

In computer science, the idea of stacks & queues can be seen in numerous ways. Any app that makes use of a shopping cart, waiting list or playlist employs a stack or queue. In programming, a call stack is often used as an essential debugging and analytics tool. For this essay, we’ll discuss the idea of stacks & queues and will review how to implement a queue in code.


Queues are based on the concept of first-in, first-out. When new objects are created, they are added to the bottom of the queue. Items in the queue are preserved in order until requested. When a request is made, the top level item is removed and is sent to the client.


In their basic form, stacks & queues employ the same structure and only vary in their use. The data structure common to both forms is the linked list. Using generics, we’ll build a queue to hold any type of object. In addition, the class will also support nil values.

//generic queue data object

class QNode<T> {
    var key: T?
    var next: QNode?


The process of adding items is often referred to as enqueuing. Here, we define the method used to enqueue objects and identify the property top that will serve as our starting point.

public class Queue<T> {

    //enqueue the specified object
    func enQueue(key: T) {
        //check for the instance
        if (top == nil) {
            top = QNode<T>()
        //establish the top node
        if (top.key == nil) {
            top.key = key
        let childToUse: QNode<T> = QNode<T>()
        var current: QNode = top
        //cycle through the list
        while ( != nil) {
            current =!
        //append a new item
        childToUse.key = key = childToUse


The process to enqueue items is similar to building a generic linked list. However, since queued items can be removed as well as added, we must ensure that our structure supports the absence of values (e.g. nil). As a result, the class property top is defined as an implicit unwrapped optional.

To keep the queue generic, the enQueue method signature also has a parameter that is declared as type T. With Swift, generics usage not only preserves type information, but also ensures objects conform to various protocols.


Dequeueing Objects

Removing items from the queue is called dequeuing.  As shown, dequeueing is a two-step process that involves returning the top-level item and reorganizing the queue.

   //retrieve top items - O(1)
   func deQueue() -> T? {
        //determine if the key or instance exists
        let topitem: T? =
        if (topitem == nil) {
            return nil
        //retrieve and queue the next item
        var queueitem: T? = top.key!

        //use optional binding
        if let nextitem = {
          top = nextitem
        else {
            top = nil
        return queueitem

When dequeuing, it is vital to know when values are absent. With deQueue, we account for the potential absence of a key in addition to an empty queue. In Swift, one must use specific techniques like optional chaining to check for nil values.


Along with adding and removing items, supporting functions also include checking for an empty queue, counting items, as well as retrieving the top level item.

    //the number of items
    var count: Int {
        if (top.key == nil) {
            return 0
        else  {
            var current: QNode<T> = top
            var x: Int = 1
            //cycle through the list of items
            while ( != nil) {
                current =!
            return x

    //retrieve the top level item
    func peek() -> T? {
        return top.key!
    //check for the presence of a value
    func isEmpty() -> Bool {
        if let _: T = {
            return false
        else {
            return true


In this example, our queue provides O(n) for insertion and O(1) for lookup. As noted, stacks support the same basic structure and generally provide O(1) for both storage and lookup. Similar to linked lists, stacks & queues play an important role when managing other data structures and algorithms.