Implement queue using stack in Go

Key takeaways:
Two stacks can form one queue: We can implement a queue using two stacks, showing how different data structures can work together.
Time complexity considerations: Enqueue is efficient at $O(1)$ , while dequeue can take $O(n)$ in the worst case, highlighting trade-offs with this approach.
Space complexity: Both stacks may hold all queue elements, so the method requires $O(n)$ space.

Understanding data structures like stacks and queues is important for efficient problem-solving. These structures form the foundation of many core algorithms in Computer Science. A stack operates on the Last-In-First-Out (LIFO) principle, while a queue follows First-In-First-Out (FIFO).

Explore the differences between the LIFO and FIFO techniques in this Answer: What is the difference between LIFO and FIFO?.

In this Answer, we’ll explore how to implement a queue using two stacks in Go, combining these two fundamental data structures to solve common interview questions.

What is a queue?

A queue is a linear data structure that organizes elements in a specific order, adhering to the First-In-First-Out (FIFO) principle. In a queue, items are added at the end through the enqueue operation and removed from the front using the dequeue operation. These core functionalities ensure that elements are processed in the exact order they are added, making queues ideal for various applications such as task scheduling, print job managementQueues manage the order of print jobs, ensuring they are processed one at a time based on when they were submitted to the printer. This allows for efficient handling of multiple requests, enabling users to continue working without delays caused by printing., and breadth-first traversals in graph algorithms.

Find out more about breadth-first traversals in this Answer: What is Breadth-First Search?

Implementing queue using stacks

We can implement a queue using two stacks. The first stack, known as the input stack, is responsible for handling the enqueue operations, while the second stack, called the output stack, manages the dequeue operations. When a dequeue request is made, elements are transferred from the input stack to the output stack. This transfer reverses the order of the elements, effectively maintaining the First-In-First-Out (FIFO) behavior of the queue. By making the use of the Last-In-First-Out (LIFO) nature of stacks for temporary storage, this approach preserves the fundamental functionality of a queue.

Let's look at the following illustration for a better understanding.

package main
import (
	"fmt"
)
// QueueUsingStacks struct holds two stacks for queue implementation
type QueueUsingStacks struct {
	inputStack  []int // Stack for enqueue operations
	outputStack []int // Stack for dequeue operations
}
// Enqueue adds a new value to the queue
func (qs *QueueUsingStacks) Enqueue(value int) {
	qs.inputStack = append(qs.inputStack, value) // Push value onto the input stack
}
// dequeueFromInput transfers all elements from the input stack to the output stack
func (qs *QueueUsingStacks) dequeueFromInput() {
	// Transfer elements to reverse their order for FIFO behavior
	for len(qs.inputStack) > 0 {
		top := qs.inputStack[len(qs.inputStack)-1] // Get the top element
		qs.inputStack = qs.inputStack[:len(qs.inputStack)-1] // Remove top element from input stack
		qs.outputStack = append(qs.outputStack, top) // Push it onto the output stack
	}
}
// Dequeue removes and returns the front element of the queue
func (qs *QueueUsingStacks) Dequeue() int {
	// If output stack is empty, transfer elements from input stack
	if len(qs.outputStack) == 0 {
		qs.dequeueFromInput()
	}
	// Return the top element from the output stack if available
	if len(qs.outputStack) > 0 {
		top := qs.outputStack[len(qs.outputStack)-1] // Get the front element
		qs.outputStack = qs.outputStack[:len(qs.outputStack)-1] // Remove it from output stack
		return top // Return the dequeued value
	}
	return -1 // Return -1 if the queue is empty
}
func main() {
	queue := &QueueUsingStacks{} // Create a new queue instance
	// Enqueue elements
	queue.Enqueue(10)
	queue.Enqueue(20)
	queue.Enqueue(30)
	
  fmt.Println("Three elements are enqueued in the following order: 10, 20, and 30.")
  
  fmt.Println("\nNow, let's dequeue three times!")
	// Dequeue elements and print the results
	fmt.Println("\nDequeue:", queue.Dequeue()) // Should print 10
	fmt.Println("Dequeue:", queue.Dequeue()) // Should print 20
	fmt.Println("Dequeue:", queue.Dequeue()) // Should print 30
}

Now, let's go over the code explanation:

Lines 8–11: The QueueUsingStacks struct defines the data structure for implementing a queue using two stacks. It contains two slices to handle queue operations:
- inputStack: This slice represents the first stack, used for enqueuing elements.
- outputStack: This slice represents the second stack, used for dequeuing elements.
Lines 14–16: The Enqueue method adds a new element to the queue by appending it to the inputStack, effectively enqueuing the element.
Lines 19–26: The dequeueFromInput function transfers elements from the inputStack to the outputStack, reversing their order in the process. It iterates through the inputStack, popping elements from the top and pushing them onto the outputStack.
Lines 29–41: The Dequeue method removes and returns the front element from the queue.
- Lines 31–33: If the outputStack is empty, the method calls dequeueFromInput to transfer elements from the inputStack to the outputStack.
- Lines 35–39: The method then pops the top element from the outputStack, effectively dequeuing the element.

Time complexity

Enqueue operation: The Enqueue method appends an element to the inputStack, which is a constant-time operation. Therefore, the time complexity for the enqueue operation is $O(1)$ .
Dequeue operation: If the outputStack is empty when Dequeue is called, all elements from the inputStack must be transferred to the outputStack, which requires iterating through n elements, where n is the number of elements in the queue. This transfer operation takes linear time. If outputStack is not empty, the Dequeue operation is $O(1)$ , as it simply pops the top element from the outputStack. Therefore, the overall time complexity for the dequeue operation is $O(n)$ in the worst case.

Space complexity

For both the enqueue and dequeue operations, the space used is proportional to the number of elements in the queue, as both inputStack and outputStack together can store all n elements. Therefore, the overall space complexity is linear in terms of the number of elements, $O(n)$ .

On that note, take a look at some other Answers that cover the similar topics:

Frequently asked questions

Haven’t found what you were looking for? Contact Us

How many stacks does it take to make a queue?

It takes two stacks to make a queue. By using one stack for enqueue operations and the other for dequeue operations, you can maintain the FIFO (First-In-First-Out) order of the queue. When dequeueing, if the second stack is empty, you transfer elements from the first stack to the second stack, reversing their order and allowing for proper dequeuing.

Can stacks be made by using 2 queues?

Yes, you can implement a stack using two queues by using one queue for enqueue operations and the other for dequeue operations, adjusting the order of elements to maintain the Last-In-First-Out (LIFO) behavior.

What is the difference between stacks and queues?

The main differences between stacks and queues are:

Order of Operations:

– Stack: Follows Last-In-First-Out (LIFO) order, meaning the last element added is the first one removed. – Queue: Follows First-In-First-Out (FIFO) order, meaning the first element added is the first one removed.

Basic Operations:

– Stack: Has two primary operations: push (to add an element) and pop (to remove the top element). – Queue: Has two primary operations: enqueue (to add an element to the end) and dequeue (to remove the front element).

Use Cases:

– Stack: Often used in scenarios like function call management, undo mechanisms in applications, and parsing expressions. – Queue: Commonly used in scheduling tasks, managing requests in a service, and breadth-first search algorithms.

Why use stack instead of queue?

You might choose to use a stack instead of a queue for the following reasons:

LIFO behavior: If your application requires the last added item to be processed first, a stack’s Last-In-First-Out (LIFO) nature is ideal.
Function call management: Stacks are used to manage function calls in programming languages (call stack), allowing for efficient backtracking and memory management.
Simpler implementation: For certain algorithms, such as depth-first search (DFS) or backtracking, implementing a stack can be simpler and more efficient than using a queue.
Space efficiency: In some cases, stacks can use less memory overhead than queues, particularly when handling recursive functions or temporary storage needs.
Specific use cases: Certain data processing tasks, like undo mechanisms in applications (where the most recent action should be reversed first), are naturally suited to a stack’s structure.

What are advantages of using a queue over a stack?

Here are some advantages of using a queue over a stack:

FIFO order: Queues follow a First-In-First-Out (FIFO) principle, making them ideal for scenarios where you need to process items in the order they were added, such as scheduling tasks or handling requests.
Balance during management: In situations where multiple tasks or processes are competing for resources, queues ensure that all requests are handled fairly, preventing starvation of earlier tasks.
Easier management of tasks: Queues are well-suited for scenarios like print job management or task scheduling in operating systems, where tasks need to be executed in the order they arrive.
Concurrency handling: Queues can be more effective in multi-threaded environments, allowing multiple threads to enqueue and dequeue tasks safely without conflicts.
Real-time processing: For applications that require real-time processing, such as streaming data or event handling, queues can efficiently manage incoming data in the order it arrives.

Free Resources