DSA Tutorial #3: Stacks and Queues — LIFO and FIFO Explained

Stacks and queues are two of the most fundamental data structures in computer science. They are building blocks for many algorithms and appear frequently in coding interviews. The rules are simple — stacks follow Last In, First Out (LIFO), and queues follow First In, First Out (FIFO).

In this article, you will learn how stacks and queues work, how to implement them, and how to solve classic interview problems. We show every example in Kotlin, Python, and Go.

What is a Stack?

A stack is a data structure where the last element added is the first one removed. This is called LIFO — Last In, First Out.

Think of a stack of plates. You put plates on top. When you take a plate, you take the one from the top. You cannot take a plate from the middle or bottom without removing the ones above it.

Stack Operations

Operation	Description	Time
push	Add element to top	O(1)
pop	Remove element from top	O(1)
peek / top	Look at top element without removing	O(1)
isEmpty	Check if stack is empty	O(1)

Stack Implementation

Most languages have a built-in stack or you can use a dynamic array.

Kotlin:

fun main() {
    val stack = ArrayDeque<Int>()

    // Push elements
    stack.addLast(10)
    stack.addLast(20)
    stack.addLast(30)

    // Peek - look at top
    println(stack.last()) // 30

    // Pop - remove from top
    println(stack.removeLast()) // 30
    println(stack.removeLast()) // 20

    // Check if empty
    println(stack.isEmpty()) // false
}

Python:

# Use a list as a stack
stack = []

# Push elements
stack.append(10)
stack.append(20)
stack.append(30)

# Peek - look at top
print(stack[-1])  # 30

# Pop - remove from top
print(stack.pop())  # 30
print(stack.pop())  # 20

# Check if empty
print(len(stack) == 0)  # False

Go:

package main

import "fmt"

func main() {
    // Use a slice as a stack
    stack := []int{}

    // Push elements
    stack = append(stack, 10)
    stack = append(stack, 20)
    stack = append(stack, 30)

    // Peek - look at top
    fmt.Println(stack[len(stack)-1]) // 30

    // Pop - remove from top
    top := stack[len(stack)-1]
    stack = stack[:len(stack)-1]
    fmt.Println(top) // 30
}

Valid Parentheses

This is the most classic stack problem in coding interviews. Given a string with brackets (), {}, [], determine if every opening bracket has a matching closing bracket in the correct order.

The idea: push opening brackets onto the stack. When you see a closing bracket, pop from the stack and check if it matches.

Kotlin:

fun isValid(s: String): Boolean {
    val stack = ArrayDeque<Char>()
    val pairs = mapOf(')' to '(', '}' to '{', ']' to '[')

    for (char in s) {
        if (char in "({[") {
            stack.addLast(char)
        } else {
            if (stack.isEmpty() || stack.removeLast() != pairs[char]) {
                return false
            }
        }
    }
    return stack.isEmpty()
}

Python:

def is_valid(s: str) -> bool:
    stack = []
    pairs = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in '({[':
            stack.append(char)
        else:
            if not stack or stack.pop() != pairs[char]:
                return False

    return len(stack) == 0

Go:

func isValid(s string) bool {
    stack := []rune{}
    pairs := map[rune]rune{')': '(', '}': '{', ']': '['}

    for _, char := range s {
        if char == '(' || char == '{' || char == '[' {
            stack = append(stack, char)
        } else {
            if len(stack) == 0 || stack[len(stack)-1] != pairs[char] {
                return false
            }
            stack = stack[:len(stack)-1]
        }
    }
    return len(stack) == 0
}

Time complexity: O(n). Space complexity: O(n) in the worst case (all opening brackets).

What is a Queue?

A queue is a data structure where the first element added is the first one removed. This is called FIFO — First In, First Out.

Think of a line at a coffee shop. The first person in line gets served first. New people join at the back of the line.

Queue Operations

Operation	Description	Time
enqueue	Add element to back	O(1)
dequeue	Remove element from front	O(1)
peek / front	Look at front element	O(1)
isEmpty	Check if queue is empty	O(1)

Queue Implementation

Kotlin:

import java.util.LinkedList

fun main() {
    val queue: java.util.Queue<Int> = LinkedList()

    // Enqueue
    queue.add(10)
    queue.add(20)
    queue.add(30)

    // Peek - look at front
    println(queue.peek()) // 10

    // Dequeue - remove from front
    println(queue.poll()) // 10
    println(queue.poll()) // 20
}

Python:

from collections import deque

queue = deque()

# Enqueue
queue.append(10)
queue.append(20)
queue.append(30)

# Peek - look at front
print(queue[0])  # 10

# Dequeue - remove from front
print(queue.popleft())  # 10
print(queue.popleft())  # 20

Go:

package main

import "fmt"

func main() {
    // Simple queue using a slice
    queue := []int{}

    // Enqueue
    queue = append(queue, 10)
    queue = append(queue, 20)
    queue = append(queue, 30)

    // Peek - look at front
    fmt.Println(queue[0]) // 10

    // Dequeue - remove from front
    front := queue[0]
    queue = queue[1:]
    fmt.Println(front) // 10
}

Note: In Go, using queue[1:] for dequeue is O(1) for the operation itself, but the underlying memory is not freed until the slice is garbage collected. For production code, use a proper ring buffer or the container/list package.

Implement Queue Using Two Stacks

This is a popular interview question. The trick: use one stack for enqueue and another for dequeue. When you need to dequeue, transfer all elements from the first stack to the second stack (which reverses the order).

Kotlin:

class MyQueue {
    private val pushStack = ArrayDeque<Int>()
    private val popStack = ArrayDeque<Int>()

    fun push(x: Int) {
        pushStack.addLast(x)
    }

    fun pop(): Int {
        if (popStack.isEmpty()) {
            while (pushStack.isNotEmpty()) {
                popStack.addLast(pushStack.removeLast())
            }
        }
        return popStack.removeLast()
    }

    fun peek(): Int {
        if (popStack.isEmpty()) {
            while (pushStack.isNotEmpty()) {
                popStack.addLast(pushStack.removeLast())
            }
        }
        return popStack.last()
    }

    fun empty(): Boolean = pushStack.isEmpty() && popStack.isEmpty()
}

Python:

class MyQueue:
    def __init__(self):
        self.push_stack = []
        self.pop_stack = []

    def push(self, x: int) -> None:
        self.push_stack.append(x)

    def pop(self) -> int:
        if not self.pop_stack:
            while self.push_stack:
                self.pop_stack.append(self.push_stack.pop())
        return self.pop_stack.pop()

    def peek(self) -> int:
        if not self.pop_stack:
            while self.push_stack:
                self.pop_stack.append(self.push_stack.pop())
        return self.pop_stack[-1]

    def empty(self) -> bool:
        return not self.push_stack and not self.pop_stack

Go:

type MyQueue struct {
    pushStack []int
    popStack  []int
}

func (q *MyQueue) Push(x int) {
    q.pushStack = append(q.pushStack, x)
}

func (q *MyQueue) transfer() {
    if len(q.popStack) == 0 {
        for len(q.pushStack) > 0 {
            top := q.pushStack[len(q.pushStack)-1]
            q.pushStack = q.pushStack[:len(q.pushStack)-1]
            q.popStack = append(q.popStack, top)
        }
    }
}

func (q *MyQueue) Pop() int {
    q.transfer()
    top := q.popStack[len(q.popStack)-1]
    q.popStack = q.popStack[:len(q.popStack)-1]
    return top
}

func (q *MyQueue) Peek() int {
    q.transfer()
    return q.popStack[len(q.popStack)-1]
}

func (q *MyQueue) Empty() bool {
    return len(q.pushStack) == 0 && len(q.popStack) == 0
}

Amortized time complexity: O(1) per operation. Each element is moved between stacks at most once.

Monotonic Stack

A monotonic stack is a stack where elements are always in increasing or decreasing order. It is a powerful technique for problems that ask “find the next greater element” or “find the next smaller element.”

Next Greater Element

Given an array, for each element find the next element that is greater. If there is no greater element, return -1.

Kotlin:

fun nextGreaterElement(nums: IntArray): IntArray {
    val result = IntArray(nums.size) { -1 }
    val stack = ArrayDeque<Int>() // stores indices

    for (i in nums.indices) {
        while (stack.isNotEmpty() && nums[stack.last()] < nums[i]) {
            result[stack.removeLast()] = nums[i]
        }
        stack.addLast(i)
    }
    return result
}

Python:

def next_greater_element(nums: list) -> list:
    result = [-1] * len(nums)
    stack = []  # stores indices

    for i in range(len(nums)):
        while stack and nums[stack[-1]] < nums[i]:
            result[stack.pop()] = nums[i]
        stack.append(i)

    return result

Go:

func nextGreaterElement(nums []int) []int {
    result := make([]int, len(nums))
    for i := range result {
        result[i] = -1
    }
    stack := []int{} // stores indices

    for i := 0; i < len(nums); i++ {
        for len(stack) > 0 && nums[stack[len(stack)-1]] < nums[i] {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            result[top] = nums[i]
        }
        stack = append(stack, i)
    }
    return result
}

For input [2, 1, 4, 3], the output is [4, 4, -1, -1]. The next greater element after 2 is 4. The next greater element after 1 is 4. There is no greater element after 4 or 3.

Time complexity: O(n) — each element is pushed and popped at most once.

When to Use Stacks vs Queues

Use a Stack when…	Use a Queue when…
You need LIFO order	You need FIFO order
Matching brackets/parentheses	Processing items in order
Undo/redo functionality	BFS (breadth-first search)
DFS (depth-first search)	Task scheduling
Expression evaluation	Message queues

Why Interviewers Ask Stack and Queue Questions

These questions test:

Understanding of LIFO vs FIFO — knowing which structure fits which problem
Implementing with constraints — building a queue from stacks shows creative thinking
Pattern recognition — recognizing when a monotonic stack solves the problem
Edge case handling — empty stack pops, underflow conditions

Practice Problems

Try these problems on LeetCode:

Valid Parentheses (LeetCode #20) — classic stack problem
Min Stack (LeetCode #155) — stack that supports getMin in O(1)
Implement Queue using Stacks (LeetCode #232) — two-stack technique
Next Greater Element I (LeetCode #496) — monotonic stack
Daily Temperatures (LeetCode #739) — monotonic stack variation

What’s Next?

In the next article, we cover Hash Maps and Sets — data structures that give you O(1) average-time lookups. Hash maps are the most useful data structure for coding interviews after arrays.

Next: DSA Tutorial #4: Hash Maps and Sets

Full series: DSA from Zero to Interview Ready

What is a Stack?#

Stack Operations#

Stack Implementation#

Valid Parentheses#

What is a Queue?#

Queue Operations#

Queue Implementation#

Implement Queue Using Two Stacks#

Monotonic Stack#

Next Greater Element#

When to Use Stacks vs Queues#

Why Interviewers Ask Stack and Queue Questions#

Practice Problems#

What’s Next?#

What is a Stack?

Stack Operations

Stack Implementation

Valid Parentheses

What is a Queue?

Queue Operations

Queue Implementation

Implement Queue Using Two Stacks

Monotonic Stack

Next Greater Element

When to Use Stacks vs Queues

Why Interviewers Ask Stack and Queue Questions

Practice Problems

What’s Next?