Solving Implement Stack using Queues in Go: Step-by-Step Guide

Introduction to Implementing Stack Using Queues in Go

Data structures form the backbone of efficient software, and sometimes interview-style problems push us to rethink how fundamental structures can be built from one another. One classic challenge is implementing a Stack using only Queues. In this tutorial, we will explore what this problem means, why it matters, and how to solve it cleanly in Go.

What Is a Stack?

A stack is a Last-In-First-Out (LIFO) data structure. The last element pushed onto the stack is the first one to be popped out. Stacks expose two primary operations:

• Push(x) — add an element to the top
• Pop() — remove and return the top element
• Top() — peek at the top element without removing it
• Empty() — check whether the stack is empty

What Is a Queue?

A queue is a First-In-First-Out (FIFO) data structure. Elements are added at the back and removed from the front. Go does not ship with a built-in queue type, but we can simulate one using slices or the container/list package.

Why This Problem Matters

Implementing a stack using queues is a popular interview question because it tests two things at once: your understanding of LIFO vs FIFO semantics, and your ability to manipulate auxiliary data structures to invert behavior. Beyond interviews, the exercise teaches important lessons about amortized cost, state management, and how higher-level abstractions can be composed from simpler primitives.

In real-world systems, you may face constraints where only a queue-like interface is available (for example, a message broker with FIFO guarantees), and you need LIFO semantics on top of it. Understanding this transformation gives you the tools to build the behavior you need.

Approaches to Solve the Problem

There are two well-known strategies for implementing a stack with queues:

• Two-queue, push-costly: Make Push O(n) and Pop O(1).
• Two-queue, pop-costly: Make Push O(1) and Pop O(n).

There is also a single-queue variant where, on each push, we rotate the queue so the newest element sits at the front. We will implement this single-queue approach because it is elegant and easy to reason about.

The Single-Queue Strategy

The idea is simple: whenever we push a new element, we add it to the back of the queue and then rotate the queue by size - 1 elements. After rotation, the newly inserted element becomes the front of the queue, mimicking the top of a stack.

This makes Push O(n) and all other operations O(1).

Implementing the Stack in Go

Let us build the solution step by step. We will use a Go slice as the underlying queue for simplicity, but the same logic works with container/list or any FIFO abstraction.

Step 1: Define the Stack Type

package main

import "fmt"

// MyStack implements a LIFO stack using a single queue (slice-backed).
type MyStack struct {
    queue []int
}

// Constructor returns a new empty stack.
func Constructor() MyStack {
    return MyStack{
        queue: []int{},
    }
}

Here we declare a struct holding a slice of integers. The Constructor function returns an initialized empty stack, mirroring the pattern used in LeetCode-style problems.

Step 2: Implement Push

// Push adds an element to the top of the stack.
func (s *MyStack) Push(x int) {
    s.queue = append(s.queue, x)
    // Rotate the queue so the new element is at the front.
    for i := 0; i < len(s.queue)-1; i++ {
        s.queue = append(s.queue, s.queue[0])
        s.queue = s.queue[1:]
    }
}

After appending the new value, we move every element that was already in the queue from the front to the back. This places the newly pushed element at the front, making it the next one to be popped.

Step 3: Implement Pop and Top

// Pop removes and returns the top element of the stack.
func (s *MyStack) Pop() int {
    if len(s.queue) == 0 {
        panic("pop from empty stack")
    }
    top := s.queue[0]
    s.queue = s.queue[1:]
    return top
}

// Top returns the top element without removing it.
func (s *MyStack) Top() int {
    if len(s.queue) == 0 {
        panic("top from empty stack")
    }
    return s.queue[0]
}

Because Push already keeps the most recent element at the front of the queue, popping is just a dequeue operation. Top peeks at the front without modifying the queue.

Step 4: Implement Empty

// Empty reports whether the stack has no elements.
func (s *MyStack) Empty() bool {
    return len(s.queue) == 0
}

Step 5: Put It All Together

package main

import "fmt"

type MyStack struct {
    queue []int
}

func Constructor() MyStack {
    return MyStack{queue: []int{}}
}

func (s *MyStack) Push(x int) {
    s.queue = append(s.queue, x)
    for i := 0; i < len(s.queue)-1; i++ {
        s.queue = append(s.queue, s.queue[0])
        s.queue = s.queue[1:]
    }
}

func (s *MyStack) Pop() int {
    if len(s.queue) == 0 {
        panic("pop from empty stack")
    }
    top := s.queue[0]
    s.queue = s.queue[1:]
    return top
}

func (s *MyStack) Top() int {
    if len(s.queue) == 0 {
        panic("top from empty stack")
    }
    return s.queue[0]
}

func (s *MyStack) Empty() bool {
    return len(s.queue) == 0
}

func main() {
    s := Constructor()
    s.Push(1)
    s.Push(2)
    s.Push(3)

    fmt.Println("Top:", s.Top())   // Output: Top: 3
    fmt.Println("Pop:", s.Pop())   // Output: Pop: 3
    fmt.Println("Pop:", s.Pop())   // Output: Pop: 2
    fmt.Println("Empty:", s.Empty()) // Output: Empty: false
    fmt.Println("Pop:", s.Pop())   // Output: Pop: 1
    fmt.Println("Empty:", s.Empty()) // Output: Empty: true
}

Running this program demonstrates correct LIFO behavior: elements come out in reverse order of insertion, exactly as a stack should behave.

Alternative: Two-Queue Pop-Costly Approach

For completeness, here is the two-queue variant where Push is O(1) and Pop is O(n). We keep one queue as the main storage and a temporary queue to reverse the order during pop.

type MyStack2 struct {
    q1 []int
    q2 []int
}

func Constructor2() MyStack2 {
    return MyStack2{}
}

func (s *MyStack2) Push(x int) {
    s.q1 = append(s.q1, x)
}

func (s *MyStack2) Pop() int {
    for len(s.q1) > 1 {
        s.q2 = append(s.q2, s.q1[0])
        s.q1 = s.q1[1:]
    }
    top := s.q1[0]
    s.q1 = s.q1[1:]
    // Swap queues
    s.q1, s.q2 = s.q2, s.q1
    return top
}

func (s *MyStack2) Top() int {
    val := s.Pop()
    s.Push(val)
    return val
}

func (s *MyStack2) Empty() bool {
    return len(s.q1) == 0
}

Notice how Top reuses Pop and then re-pushes the value. This is a common pattern when one operation is naturally expensive and the other can piggyback on it.

Best Practices

• Choose the right trade-off: If your workload is push-heavy, prefer the pop-costly approach. If it is pop-heavy, prefer the push-costly approach.
• Avoid panics in production code: Replace panic calls with proper error returns or sentinel values like (0, false).
• Use generics for reusability: In Go 1.18+, parameterize the stack with type parameters so it works with any type, not just int.
• Prefer container/list for large datasets: Slices cause allocations on growth; a linked list avoids the rotation cost of copying.
• Write table-driven tests: Cover edge cases like popping from an empty stack, pushing duplicates, and interleaving operations.

type Stack[T any] struct {
    queue []T
}

func (s *Stack[T]) Push(x T) {
    s.queue = append(s.queue, x)
    for i := 0; i < len(s.queue)-1; i++ {
        s.queue = append(s.queue, s.queue[0])
        s.queue = s.queue[1:]
    }
}

func (s *Stack[T]) Pop() (T, bool) {
    var zero T
    if len(s.queue) == 0 {
        return zero, false
    }
    top := s.queue[0]
    s.queue = s.queue[1:]
    return top, true
}