Implement Stack Using Queue in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Push and Pop Operations on Stack Implemented Using One Queue

Consider a stack implemented using a single queue. The push operation adds an element, and the pop operation removes the last pushed element. What is the output after the following operations?

push(10), push(20), push(30), pop(), pop()

DSA Go

package main

import "fmt"

type Stack struct {
    queue []int
}

func (s *Stack) 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 *Stack) Pop() int {
    if len(s.queue) == 0 {
        return -1
    }
    top := s.queue[0]
    s.queue = s.queue[1:]
    return top
}

func main() {
    s := Stack{}
    s.Push(10)
    s.Push(20)
    s.Push(30)
    fmt.Println(s.Pop())
    fmt.Println(s.Pop())
}

A 20\n30

B 10\n20

C 30\n10

D 30\n20

💡 Hint

Remember that push rotates the queue to keep the last pushed element at the front.

The push operation rotates the queue so the last pushed element is always at the front. Thus, pop removes the most recently pushed element first, following stack behavior.

❓ Predict Output

intermediate

Output of Pop on Empty Stack Implemented Using Two Queues

Given a stack implemented using two queues, what is the output of the pop operation when the stack is empty?

DSA Go

package main

import "fmt"

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

func (s *Stack) Pop() int {
    if len(s.q1) == 0 {
        return -1
    }
    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[:0]
    s.q1, s.q2 = s.q2, s.q1
    return top
}

func main() {
    s := Stack{}
    fmt.Println(s.Pop())
}

A 0

B panic: index out of range

C -1

D nil

💡 Hint

Check how the code handles empty queue before popping.

The pop method checks if the main queue is empty and returns -1 to indicate the stack is empty, avoiding runtime errors.

❓ Predict Output

advanced

Final Queue State After Push and Pop in Stack Using Two Queues

What is the state of the main queue after these operations on a stack implemented with two queues?

push(5), push(10), pop(), push(15), pop()

DSA Go

package main

import "fmt"

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

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

func (s *Stack) Pop() int {
    if len(s.q1) == 0 {
        return -1
    }
    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[:0]
    s.q1, s.q2 = s.q2, s.q1
    return top
}

func main() {
    s := Stack{}
    s.Push(5)
    s.Push(10)
    s.Pop()
    s.Push(15)
    s.Pop()
    fmt.Println(s.q1)
}

A [5]

B [15]

C []

D [10, 15]

💡 Hint

Trace the elements moved between queues during pop.

After the first pop, 10 is removed leaving 5. After pushing 15 and popping, 15 is removed leaving 5 in the main queue.

🧠 Conceptual

advanced

Time Complexity of Push and Pop in Stack Using One Queue

What is the time complexity of push and pop operations in a stack implemented using a single queue where push rotates the queue to maintain stack order?

A Push: O(1), Pop: O(n)

B Push: O(n), Pop: O(1)

C Push: O(n), Pop: O(n)

D Push: O(1), Pop: O(1)

💡 Hint

Consider how many elements are moved during push and pop.

Push operation rotates the queue by moving all elements except the new one, so it takes O(n). Pop just removes the front element, O(1).

❓ Predict Output

expert

Output of Sequence of Operations on Stack Using One Queue

Given the following sequence of operations on a stack implemented using one queue, what is the printed output?

push(1), push(2), pop(), push(3), pop(), pop()

DSA Go

package main

import "fmt"

type Stack struct {
    queue []int
}

func (s *Stack) 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 *Stack) Pop() int {
    if len(s.queue) == 0 {
        return -1
    }
    top := s.queue[0]
    s.queue = s.queue[1:]
    return top
}

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

A 2\n3\n1

B 1\n3\n2

C 3\n2\n1

D 2\n1\n3

💡 Hint

Remember push rotates queue to keep last pushed element at front.

Push rotates queue so last pushed is front. Pops remove 2, then 3, then 1 in order.

Practice

1. What is the main idea behind implementing a stack using a queue?

easy

A. Use one or two queues to simulate Last-In-First-Out (LIFO) behavior

B. Use a queue to store elements in sorted order

C. Use a stack to simulate First-In-First-Out (FIFO) behavior

D. Use two stacks to implement a queue

Solution

1. Step 1: Understand stack and queue behaviors

   A stack follows Last-In-First-Out (LIFO), while a queue follows First-In-First-Out (FIFO).

2. Step 2: Simulate stack using queue(s)

   To implement a stack using queue(s), we use one or two queues to reorder elements so the last pushed element is always dequeued first.

3. Final Answer:

   Use one or two queues to simulate Last-In-First-Out (LIFO) behavior -> Option A

4. Quick Check:

   Stack = LIFO simulated by queue(s) [OK]

Hint: Remember stack is LIFO; queue is FIFO, reorder to simulate stack [OK]

Common Mistakes:

• Confusing stack and queue order
• Trying to sort elements instead of reordering
• Using stack to implement queue instead

2. Which of the following is the correct Go syntax to declare a queue using a slice of integers?

easy

A. var queue []int

B. queue := make(map[int]int)

C. queue := []string{}

D. var queue int

Solution

1. Step 1: Identify queue data structure type

   A queue can be implemented using a slice of integers for integer elements.

2. Step 2: Check Go syntax for slice declaration

   "var queue []int" declares a slice of integers, suitable for queue implementation.

3. Final Answer:

   var queue []int -> Option A

4. Quick Check:

   Slice of int = queue [OK]

Hint: Use slice []int for queue of integers in Go [OK]

Common Mistakes:

• Using map instead of slice for queue
• Declaring wrong data type for queue
• Using string slice for integer queue

3. Consider this Go code snippet implementing push operation of stack using one queue:

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

If initially s.q = [1, 2], what is s.q after calling Push(3)?

medium

A. [3, 2, 1]

B. [1, 2, 3]

C. [3, 1, 2]

D. [2, 1, 3]

Solution

1. Step 1: Append new element 3 to queue

   Initial queue: [1, 2]. After append: [1, 2, 3].

2. Step 2: Rotate queue elements to move 3 to front

   Loop runs len(s.q)-1 = 2 times: - Iteration 1: append s.q[0]=1, queue becomes [1, 2, 3, 1], then remove first element: [2, 3, 1] - Iteration 2: append s.q[0]=2, queue becomes [2, 3, 1, 2], then remove first element: [3, 1, 2]

3. Final Answer:

   [3, 1, 2] -> Option C

4. Quick Check:

   Push moves new element front: [3,1,2] [OK]

Hint: New push rotates queue to front [OK]

Common Mistakes:

• Not rotating queue after append
• Removing wrong elements during rotation
• Confusing order of elements after push

4. This Go code tries to implement Pop operation for stack using one queue:

func (s *Stack) Pop() int {
    if len(s.q) == 0 {
        return -1
    }
    val := s.q[0]
    s.q = s.q[1:]
    return val
}

What is the bug in this Pop method?

medium

A. It returns -1 when queue is empty, should panic instead

B. It removes the last element instead of the first

C. It does not check if queue is nil before accessing

D. It removes the front element, but stack pop should remove the last pushed element

Solution

1. Step 1: Understand Pop operation in stack

   Pop removes the last pushed element (top of stack).

2. Step 2: Analyze given Pop code

   Code removes s.q[0], the front of queue, which is incorrect because stack top is at front only if queue is rotated properly.

3. Final Answer:

   It removes the front element, but stack pop should remove the last pushed element -> Option D

4. Quick Check:

   Pop must remove last pushed, not front [OK]

Hint: Pop must remove top, not front element [OK]

Common Mistakes:

• Removing front element without rotation
• Ignoring empty queue check
• Returning wrong default value

5. You want to implement a stack using two queues q1 and q2 in Go. Which approach correctly implements the Push operation to keep the stack order?

hard

A. Dequeue all elements from q1 to q2, then enqueue new element to q1

B. Enqueue new element to q2, then dequeue all from q1 to q2, swap q1 and q2

C. Enqueue new element to q1 only, no other operations

D. Enqueue new element to q1, then dequeue one element from q2

Solution

1. Step 1: Understand two-queue stack push logic

   To keep stack order, new element must be at front of main queue after push.

2. Step 2: Push by enqueue to empty q2, move all from q1 to q2, then swap

   Enqueue new element to q2, move all q1 elements to q2, then swap q1 and q2 so q1 has new order with new element front.

3. Final Answer:

   Enqueue new element to q2, then dequeue all from q1 to q2, swap q1 and q2 -> Option B

4. Quick Check:

   Push uses q2 enqueue + q1 transfer + swap [OK]

Hint: Push to empty q2, move q1 to q2, swap queues [OK]

Common Mistakes:

• Not swapping queues after transfer
• Enqueueing new element to wrong queue
• Forgetting to move all elements