Queue vs Stack When to Use Which in DSA Go - Trade-offs & Analysis

Mental Model

A stack adds and removes items from the top only, like a pile of plates. A queue adds items at the back and removes from the front, like a line of people waiting.

Analogy: Stack is like a stack of books where you put and take from the top. Queue is like a line at a ticket counter where the first person in line is served first.

Stack (top at right): bottom -> 1 -> 2 -> 3 [top]
Queue (front at left): [front] 1 -> 2 -> 3 -> back

Dry Run Walkthrough

Input: Stack: push 1, push 2, push 3, pop Queue: enqueue 1, enqueue 2, enqueue 3, dequeue

Goal: Show how stack and queue add and remove items differently

Step 1: Push 1 onto stack

Stack: 1 [top]

Why: Start with one item on the stack

Step 2: Push 2 onto stack

Stack: 1 -> 2 [top]

Why: Add new item on top of previous

Step 3: Push 3 onto stack

Stack: 1 -> 2 -> 3 [top]

Why: Add another item on top

Step 4: Pop from stack

Stack: 1 -> 2 [top]

Why: Remove the top item (3) following last-in-first-out

Step 5: Enqueue 1 into queue

Queue: [front] 1 -> back

Why: Start queue with one item

Step 6: Enqueue 2 into queue

Queue: [front] 1 -> 2 -> back

Why: Add new item at the back

Step 7: Enqueue 3 into queue

Queue: [front] 1 -> 2 -> 3 -> back

Why: Add another item at the back

Step 8: Dequeue from queue

Queue: [front] 2 -> 3 -> back

Why: Remove the front item (1) following first-in-first-out

Result:

Stack final: 1 -> 2 [top]
Queue final: [front] 2 -> 3 -> back

Annotated Code

DSA Go

package main

import (
	"fmt"
)

type Stack struct {
	items []int
}

func (s *Stack) Push(val int) {
	s.items = append(s.items, val) // add to top
}

func (s *Stack) Pop() (int, bool) {
	if len(s.items) == 0 {
		return 0, false // empty stack
	}
	val := s.items[len(s.items)-1] // get top
	s.items = s.items[:len(s.items)-1] // remove top
	return val, true
}

type Queue struct {
	items []int
}

func (q *Queue) Enqueue(val int) {
	q.items = append(q.items, val) // add to back
}

func (q *Queue) Dequeue() (int, bool) {
	if len(q.items) == 0 {
		return 0, false // empty queue
	}
	val := q.items[0] // get front
	q.items = q.items[1:] // remove front
	return val, true
}

func main() {
	// Stack example
	stack := Stack{}
	stack.Push(1)
	stack.Push(2)
	stack.Push(3)
	popVal, _ := stack.Pop()
	fmt.Printf("Stack after pushes and one pop: %v (popped %d)\n", stack.items, popVal)

	// Queue example
	queue := Queue{}
	queue.Enqueue(1)
	queue.Enqueue(2)
	queue.Enqueue(3)
	deqVal, _ := queue.Dequeue()
	fmt.Printf("Queue after enqueues and one dequeue: %v (dequeued %d)\n", queue.items, deqVal)
}

s.items = append(s.items, val) // add to top

push new item on top of stack

val := s.items[len(s.items)-1] // get top s.items = s.items[:len(s.items)-1] // remove top

pop top item from stack

q.items = append(q.items, val) // add to back

enqueue new item at back of queue

val := q.items[0] // get front q.items = q.items[1:] // remove front

dequeue front item from queue

Output

Stack after pushes and one pop: [1 2] (popped 3)

Queue after enqueues and one dequeue: [2 3] (dequeued 1)

Complexity Analysis

Time: O(1) for push/pop in stack and enqueue/dequeue in queue because operations happen at one end only

Space: O(n) because both store all elements in memory

vs Alternative: Compared to arrays where removing from front is O(n), queue removes front in O(1) by slicing; stack is simpler with only one end

Edge Cases

empty stack pop

returns false and zero value without error

DSA Go

if len(s.items) == 0 {
	return 0, false // empty stack
}

empty queue dequeue

returns false and zero value without error

DSA Go

if len(q.items) == 0 {
	return 0, false // empty queue
}

single element stack pop

removes the only element and stack becomes empty

DSA Go

val := s.items[len(s.items)-1] // get top
	s.items = s.items[:len(s.items)-1] // remove top

single element queue dequeue

removes the only element and queue becomes empty

DSA Go

val := q.items[0] // get front
	q.items = q.items[1:] // remove front

When to Use This Pattern

When you need to process items in reverse order, use a stack; when you need to process items in the order they arrive, use a queue.

Common Mistakes

Mistake: Trying to dequeue from a stack or pop from a queue
Fix: Use pop only with stack and dequeue only with queue to respect their order rules

Mistake: Removing from front of array for queue without slicing, causing O(n) cost
Fix: Use slicing to remove front element efficiently in queue

Summary

Stack stores items last-in-first-out; queue stores items first-in-first-out.

Use stack when you want to reverse order or backtrack; use queue when order of arrival matters.

Stack adds/removes from one end; queue adds at back and removes from front.

Practice

1. Which data structure should you use when you need to process items in the exact order they arrive, like customers waiting in line?

easy

A. Queue, because it processes items in First-In-First-Out order

B. Stack, because it processes items in Last-In-First-Out order

C. Array, because it allows random access

D. Tree, because it organizes data hierarchically

Solution

1. Step 1: Understand the order requirement

   Processing items in the exact order they arrive means First-In-First-Out (FIFO).

2. Step 2: Match data structure to FIFO

   Queue follows FIFO, so it fits the requirement perfectly.

3. Final Answer:

   Queue, because it processes items in First-In-First-Out order -> Option A

4. Quick Check:

   FIFO = Queue [OK]

Hint: FIFO means use Queue, like a line at a store [OK]

Common Mistakes:

• Confusing FIFO with LIFO
• Choosing Stack for order-sensitive tasks
• Thinking arrays maintain insertion order automatically

2. Which of the following is the correct way to push an element onto a stack in Go using a slice named stack?

easy

A. stack = append(element, stack...)

B. stack = stack[:len(stack)-1]

C. stack = stack + element

D. stack = append(stack, element)

Solution

1. Step 1: Recall how to add elements to a slice

   In Go, append(slice, value) adds value to the end of slice.

2. Step 2: Identify correct push operation

   Pushing onto a stack means adding to the top, which is the end of the slice, so stack = append(stack, element) is correct.

3. Final Answer:

   stack = append(stack, element) -> Option D

4. Quick Check:

   Push = append to slice end [OK]

Hint: Use append to add on top of stack slice [OK]

Common Mistakes:

• Using slicing to add elements instead of append
• Trying to add element at the front incorrectly
• Using + operator which is invalid for slices

3. What will be the output of the following Go code snippet?

queue := []int{1, 2, 3}
// Dequeue operation
queue = queue[1:]
fmt.Println(queue)

medium

A. [2 3]

B. []

C. [3]

D. [1 2 3]

Solution

1. Step 1: Understand the dequeue operation

   Dequeue removes the first element, so slicing from index 1 removes the first element.

2. Step 2: Apply slicing to queue

   Original queue is [1 2 3], after queue = queue[1:], queue becomes [2 3].

3. Final Answer:

   [2 3] -> Option A

4. Quick Check:

   queue[1:] removes first element [OK]

Hint: queue = queue[1:] removes front element [OK]

Common Mistakes:

• Thinking queue[1:] removes last element
• Confusing slice syntax with pop operation
• Expecting original queue unchanged

4. The following Go code intends to pop an element from a stack implemented as a slice. What is the error?

stack := []int{10, 20, 30}
popped := stack[len(stack)]
stack = stack[:len(stack)-1]
fmt.Println(popped, stack)

medium

A. Syntax error due to missing parentheses

B. Index out of range error when accessing stack[len(stack)]

C. Popped element is always zero

D. Stack slice is not updated correctly

Solution

1. Step 1: Check index used for popping

   Indexing in Go slices is zero-based, so last element is at len(stack)-1, not len(stack).

2. Step 2: Identify error cause

   Accessing stack[len(stack)] causes index out of range error because it is beyond last index.

3. Final Answer:

   Index out of range error when accessing stack[len(stack)] -> Option B

4. Quick Check:

   Last index = len(stack)-1, not len(stack) [OK]

Hint: Last element index is len(slice)-1, not len(slice) [OK]

Common Mistakes:

• Using len(slice) as index instead of len(slice)-1
• Not updating slice after pop
• Confusing pop with dequeue operation

5. You need to design a system that tracks the most recent 5 user actions to allow undo functionality. Which data structure is best and why?

hard

A. Array, because it allows random access to any action

B. Queue, because it keeps actions in order and removes oldest first

C. Stack, because it allows undo by removing the most recent action first

D. Linked list, because it allows fast insertion anywhere

Solution

1. Step 1: Understand undo functionality

   Undo removes the most recent action first, which is Last-In-First-Out (LIFO) behavior.

2. Step 2: Match data structure to LIFO

   Stack follows LIFO, so it is best to track recent actions and undo them in reverse order.

3. Final Answer:

   Stack, because it allows undo by removing the most recent action first -> Option C

4. Quick Check:

   Undo = LIFO = Stack [OK]

Hint: Undo needs LIFO, so use Stack [OK]

Common Mistakes:

• Choosing Queue which removes oldest first
• Thinking array random access helps undo
• Ignoring order of undo operations