Introduction: Stacks and Queues

Welcome to an exciting exploration of two fundamental data structures: Stacks and Queues! Data structures store and organize data in a structured and efficient manner. Stacks and Queues are akin to stacking plates and standing in a line, respectively. Intriguing, isn't it? Let's dive in!

Stacks: Last In, First Out (LIFO)

A Stack adheres to the "Last In, First Out" or LIFO principle. It's like a pile of plates where the last plate added is the first one to be removed. In Go, we can simulate stack behavior using slices, which are dynamic and allow adding and removing elements easily. The primary methods we'll mimic for stack operations include Push, Pop, and Top:

  • Push: Adds an element to the top of the stack.
  • Pop: Removes the top element from the stack.
  • Top: Returns the top element of the stack without removing it.

Let's explore this in code:

package main

import (
    "fmt"
)

// Stack represents a stack using a slice
type Stack struct {
    elements []string
}

// Push adds an element to the top of the stack
func (s *Stack) Push(element string) {
    s.elements = append(s.elements, element) // Appends the element to the slice
}

// Pop removes the top element from the stack
func (s *Stack) Pop() string {
    if len(s.elements) == 0 {
        return "No elements to remove!"
    }
    topElement := s.elements[len(s.elements)-1] // Get the last element
    s.elements = s.elements[:len(s.elements)-1] // Remove the last element
    return topElement
}

// Top returns the top element of the stack without removing it
func (s *Stack) Top() string {
    if len(s.elements) == 0 {
        return "No elements in the stack!"
    }
    return s.elements[len(s.elements)-1]
}

func main() {
    stack := Stack{}
    stack.Push("Element 1")      // Adding first element
    stack.Push("Element 2")      // Adding second element

    // Checking the top element, which is "Element 2"
    fmt.Println("Top element:", stack.Top()) // Outputs: Top element: Element 2

    // Removing the top element, which is "Element 2"
    fmt.Println("Removed:", stack.Pop()) // Outputs: Removed: Element 2
}

Here, the Push function appends an element to the slice, just like adding a new plate on the top. The Pop function retrieves and removes the last element of the slice, demonstrating the LIFO behavior. The Top function retrieves the last element added without removing it, allowing us to peek at the top of the stack.

Queues: First In, First Out (FIFO)

A Queue represents the "First In, First Out" or FIFO principle, much like waiting in line at the grocery store. We can simulate queue behavior using slices in Go. The primary queue operations we'll mimic are Enqueue, Dequeue, and Front:

  • Enqueue: Adds an element to the end of the queue.
  • Dequeue: Removes the first element from the queue.
  • Front: Returns the first element of the queue without removing it.

Let's see how this queue structure turns out in code:

package main

import (
    "fmt"
)

// Queue represents a queue using a slice
type Queue struct {
    elements []string
}

// Enqueue adds an element to the end of the queue
func (q *Queue) Enqueue(element string) {
    q.elements = append(q.elements, element) // Appends the element to the slice
}

// Dequeue removes the first element from the queue
func (q *Queue) Dequeue() string {
    if len(q.elements) == 0 {
        return "No elements to dequeue!"
    }
    frontElement := q.elements[0]       // Get the first element
    q.elements = q.elements[1:]         // Remove the first element
    return frontElement
}

// Front returns the first element of the queue without removing it
func (q *Queue) Front() string {
    if len(q.elements) == 0 {
        return "No elements in the queue!"
    }
    return q.elements[0]
}

func main() {
    queue := Queue{}
    queue.Enqueue("Element 1") // Adds first element to the queue
    queue.Enqueue("Element 2") // Adds second element to the queue

    // Checking the front element, which is "Element 1"
    fmt.Println("Front element:", queue.Front()) // Outputs: Front element: Element 1

    // Removing the first element, which is "Element 1"
    fmt.Println("Removed:", queue.Dequeue()) // Outputs: Removed: Element 1
}

In this implementation, Enqueue appends elements to the slice, Dequeue retrieves and removes the first element, illustrating FIFO operation, and Front retrieves the first element without removing it, allowing us to peek at the front of the queue.

Mastering Stack and Queue Operations With a Text Editor

Let's depict the two structures within a real-life context using a text editor that features an Undo mechanism (that is, a Stack) and a Print Queue.

package main

import (
    "fmt"
)

// TextEditor simulates undo and print queue operations
type TextEditor struct {
    actions    []string
    printQueue []string
}

// MakeChange adds an action to the undo stack
func (t *TextEditor) MakeChange(action string) {
    t.actions = append(t.actions, action)
}

// UndoChange undoes the most recent action
func (t *TextEditor) UndoChange() string {
    if len(t.actions) == 0 {
        return "No changes to undo!"
    }
    lastAction := t.actions[len(t.actions)-1]
    t.actions = t.actions[:len(t.actions)-1]
    return lastAction
}

// AddToPrint queues a document for printing
func (t *TextEditor) AddToPrint(doc string) {
    t.printQueue = append(t.printQueue, doc)
}

// PrintDoc prints the document that has been waiting the longest
func (t *TextEditor) PrintDoc() string {
    if len(t.printQueue) == 0 {
        return "No documents in the print queue!"
    }
    nextDocument := t.printQueue[0]
    t.printQueue = t.printQueue[1:]
    return nextDocument
}

func main() {
    editor := TextEditor{}

    editor.MakeChange("Changed font size") // Adds an action to the undo stack
    editor.MakeChange("Inserted image")    // Adds another action

    // Undoing the most recent change, which should be "Inserted image"
    fmt.Println("Undo:", editor.UndoChange()) // Outputs: Undo: Inserted image

    editor.AddToPrint("Proposal.docx") // Adds a document to the print queue
    editor.AddToPrint("Report.xlsx")   // Adds another document

    // Printing the document that has been in the queue the longest, which should be "Proposal.docx"
    fmt.Println("Print:", editor.PrintDoc()) // Outputs: Print: Proposal.docx
}

This code snippet integrates the Stack and Queue concepts through a TextEditor struct. The MakeChange and UndoChange methods simulate an undo stack where actions taken are pushed onto the stack and can be undone one by one, in reverse order. On the other hand, AddToPrint and PrintDoc are modeled as a print queue, where documents are added to a queue and printed in the order they were added.

Lesson Summary

Great work! You have examined the mechanics of Stacks and Queues, both integral data structures. Remember to practice what you've learned. Happy coding!

Previous
Sign up
Join the 1M+ learners on CodeSignal
Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal