You Already Know These Data Structures [Arrays, Stacks, Queues]

Hey, DEV.to community!

Data structures are the way data are organized and accessed. This is one of the most fundamental concepts of programming and every programmer should know them well in order to utilize them and provide the program an appropriate behavior.

Although knowing these are essential, even if you haven't read about them specifically, you already know most of them and used them without knowing.

I will demonstrate the usage of each of the data structures mentioned using JavaScript and Go.

Arrays

Arrays are probably one of the first things you learn when working with a programming language. This is one of the most basic data structures that every program varying from the simplest to advanced uses.

Arrays have indices, to access the data inside them. The index usually starts at 0, so an array of length n has indices up to n-1 (Some programming languages start the array index from 1, but since this is usually not the case, we keep it considered as starting from 0).

JavaScript is a dynamic type programming language, so the arrays can have multiple data types included. But in this article, we will only use integers as a demonstration for all languages.

JavaScript array:

let x = [29, 312, 78, 213, 786]

console.log(x[0]) // 29
console.log(x[2]) // 78

In Go, an array's size is a part of its type, so arrays cannot be expanded.
Go array:

package main

import "fmt"

func main() {
    var n = [5]int{29, 312, 78, 213, 786}

    fmt.Println(n[0]) // 29
    fmt.Println(n[2]) // 78
}

The way of keeping an array in memory depends on the programming language. But what usually happens is that the elements are stored in a continuous sequence. The first element of an array is the address of the array stored in the variable, so the later items can be found easily by following the first element.

Stacks

Stack is another famous data structure. Stacks follow LIFO order, which stands for "Last In First Out" (Often referred to as FILO, "First In Last Out"). The simple understanding of a stack can be defined as a bag that you put books in it and they grow vertically, so you have to take them out from the top again. Thus you are accessing the last book you've put inside the bag first and so on.

The action of adding an element to a stack is called "push" and the action of getting an element is called "pop". When popping an element from a stack, the elements get dropped from the stack and returned.

JavaScript arrays already can act as a stack since they feature Array.prototype.push() and Array.prototype.pop():

let x = []

x.push(87)
x.push(43)

console.log(x) // [87, 43]

console.log(x.pop()) // 43
console.log(x.pop()) // 87

console.log(x) // []

But in case you wanted to make a stack class using JavaScript, you can implement it as below:

class Stack {
    #items = []

    push(item) {
        this.#items.push(item)
    }

    pop() {
        if(this.isEmpty()) return 'Underflow'
        return this.#items.pop()
    }

    isEmpty() {
        return this.#items.length === 0
    }

    get length() {
        return this.#items.length
    }

    getItems() {
        return this.#items
    }

    prettify() {
        let resultString = ''
        for(let i = 0; i < this.#items.length; i++)
            resultString += this.#items[i] + ' '
        return resultString
    }
}

let foods = new Stack

foods.push('pizza')
foods.push('hamburger')
foods.push('kebab')
foods.push('kufte')

console.log(foods.length) // 4

console.log(foods.getItems()) // [ 'pizza', 'hamburger', 'kebab', 'kufte' ]

console.log(foods.prettify()) // pizza hamburger kebab kufte

console.log(foods.pop()) // kufte
console.log(foods.pop()) // kebab
console.log(foods.pop()) // hamburger
console.log(foods.pop()) // pizza

console.log(foods.length) // 0

Golang is using slices as a replacement for dynamic arrays (though they aren't dynamic actually). Using slices we can implement a stack-like behavior in Go:

package main

import "fmt"

func main() {
    var x []int

    x = append(x, 9)
    x = append(x, 10)

    fmt.Println(x) // [9 10]

    for 0 < len(x) {
        var top = len(x) - 1
        fmt.Println(x[top])

        x = x[:top]
    }

    fmt.Println(x) // []
}

Queue

Queues are similar to Stacks. They use almost the same structure, the difference is the way they access the elements. Queues follow FIFO order, which stands "First In First Out". The element which got added to the queue first will be accessed first. Just like a queue of people, whoever stands first will get their order sooner.

The action of adding an element to a queue is called "enqueue" and the action of accessing an element is called "dequeue".

JavaScript arrays have a prototype of "unshift" defined as Array.prototype.unshift() which added the element to the beginning of the array. So using this prototype and pop prototype we can implement a queue-like behavior in JavaScript:

let x = []

x.unshift(78)
x.unshift(23)
x.unshift(56)

console.log(x) // [56, 23, 78]

console.log(x.pop()) // 78
console.log(x.pop()) // 23
console.log(x.pop()) // 56

console.log(x) // []

JavaScript arrays have another prototype called Array.prototype.shift() which deletes and returns the first element of an array. So combining push and shift can also act as a queue as well:

let x = []

x.push(78)
x.push(23)
x.push(56)

console.log(x) // [78, 23, 56]

console.log(x.shift()) // 78
console.log(x.shift()) // 23
console.log(x.shift()) // 56

console.log(x) // []

If you wanted to implement a queue class in JavaScript, you can act as below:

class Queue {
    #items = []

    enqueue(item) {
        this.#items.push(item)
    }

    dequeue() {
        if(this.isEmpty())
            return 'Underflow'
        return this.#items.shift()
    }

    isEmpty() {
        return this.#items.length === 0
    }

    front() {
        if(this.isEmpty())
            return 'No item in queue'
        return this.#items[0]
    }

    get length() {
        return this.#items.length
    }

    getItems() {
        return this.#items
    }

    prettify() {
        let resultString = ''
        for(let i = 0; i < this.#items.length; i++)
            resultString += this.#items[i] + ' '
        return resultString
    }
}

let foods = new Queue

console.log(foods.length) // 0

foods.enqueue('pizza')
foods.enqueue('hamburger')
foods.enqueue('kebab')
foods.enqueue('kufte')

console.log(foods.length) // 4

console.log(foods.getItems()) // [ 'pizza', 'hamburger', 'kebab', 'kufte' ]

console.log(foods.prettify()) // pizza hamburger kebab kufte

console.log(foods.dequeue()) // pizza
console.log(foods.dequeue()) // hamburger
console.log(foods.dequeue()) // kebab
console.log(foods.dequeue()) // kufte

console.log(foods.length) // 0

As well as stacks, we can implement a queue-like behavior in Go using slices:

package main

import "fmt"

func main() {
    var x []int

    x = append(x, 9)
    x = append(x, 10)
    x = append(x, 11)
    x = append(x, 12)

    fmt.Println(x) // [9 10 11 12]

    for 0 < len(x) {
        fmt.Println(x[0])

        x = x[1:]
    }

    fmt.Println(x) // []
}

---

I am going to explain other data structures in another post since this post was aiming to explain the data structures that are used even without getting recognized.

I hope you've enjoyed it.

BTW! Check out my free Node.js Essentials E-book here:

NodeJS Essentials | Free E-Book

Adnan Babakan (he/him) ・ Sep 11 '20

#node #javascript #books