Relearning basics of CS - Implementing Queue

urulaik — Mon, 14 Oct 2024 17:17:07 +0000

Have you ever stood in a queue, The queue data structure also does the same thing. You stand in the end of line when you want to place an order maybe in your favorite self service restaurant and then you move up the queue and leave.

The Queue data structure in CS performs the same functionality. The Queue Data structure is a First In First Out data structure. The Queue Data structure can be built with two basic functions Enqueue and Dequeue which basically is adding to the list and removing from the list.

Real life examples

In the real world of computer science Queues form the backbone of the following software components

Task scheduling
Event handling
Async communication etc

While a simple easy to visualize component would be

A queue in playlist for the songs
A queue in the order of data being sent across the network etc

Implementation

package main

import (
    "fmt"
    "errors"
)

type Queue struct{
    Elements []int
    Size int
}

func (q *Queue) Enqueue(value int){
    if q.GetLength() == q.Size { 
        fmt.Println("Overflow") 
        return
    } 
    q.Elements = append(q.Elements, value) 
}

func (q *Queue) Dequeue() int {
    if q.IsEmpty() { 
        fmt.Println("UnderFlow") 
        return 0
    } 
    element := q.Elements[0] 
    if q.GetLength() == 1 { 
        q.Elements = nil 
        return element 
    } 
    q.Elements = q.Elements[1:] 
    return element
}

func (q *Queue) GetLength() int { 
    return len(q.Elements) 
} 

func (q *Queue) IsEmpty() bool { 
    return len(q.Elements) == 0
} 

func (q *Queue) Peek() (int, error) { 
    if q.IsEmpty() { 
        return 0, errors.New("empty queue") 
    } 
    return q.Elements[0], nil 
}

Complexity

Time Complexity - O(1) for Enqueue and Dequeue
Space complexity - O(1) for Enqueue and Dequeue

References

Reference - https://www.geeksforgeeks.org/queue-in-go-language/

Relearning Basics of CS - Implementing Stack

urulaik — Sun, 13 Oct 2024 17:54:37 +0000

I have been trying to learn a new programming language and what better way to do it than start from the basics. In this series of posts that come I will attempt to implement a simple Data structure and algorithms using Go.

In the book An Introduction to algorithms By CLRS in the chapter of Elementary data structure the first data structure that is being talked about is the stack.

What is a Stack

Stack is a simple data structure that is used to store a set of items. The properties of a stack are that it allows us to add an item to the top of the stack and remove from the stack so it follows a Last In First Out principle or LIFO.

The insert operation is called a Push and the remove operation is called a Pop. Since we dont want to have an empty stack pop and deal with memory errors we also implement a check for whether a Stack is empty or not. Fairly simple data structure.

Below you can find the implementation of the stack in golang. The time complexity is O(N) and space complexity of using a stack is O(1)

package main

import "fmt"

type Stack []int

func (stack *Stack) Push (value int){
    *stack = append(*stack, value)
}

func (stack *Stack) Pop () int{
    if stack.IsEmpty() {
        return 0
    }
    top := (*stack)[len(*stack)-1]
    *stack = (*stack)[:len(*stack)-1]
    return top
}

func (stack *Stack) IsEmpty() bool{
    return len(*stack) == 0
}


func main(){
    st := Stack{}
    st.Push(1)
    st.Push(2)
    fmt.Println(st.Pop())
}