225. Implement Stack using Queues

 

Implementing a Stack Using a Queue in Java

In this blog post, we’ll explore how to implement a stack using a queue in Java. This is an interesting problem that demonstrates the versatility of data structures and how they can be manipulated to achieve desired functionalities.

Introduction

A stack is a Last-In-First-Out (LIFO) data structure, where the last element added is the first one to be removed. A queue, on the other hand, is a First-In-First-Out (FIFO) data structure. The challenge here is to implement stack operations using a queue.

Approach

To implement a stack using a queue, we need to simulate the LIFO behavior using the FIFO nature of the queue. Here’s how we achieve this:

  1. Push Operation:

    • Simply add the element to the queue.

  2. Pop Operation:

    • Transfer all elements from the queue to an array.
    • Re-add all elements except the last one back to the queue.
    • Return the last element from the array.

  3. Top Operation:

    • Similar to pop, transfer all elements to an array.
    • Re-add all elements back to the queue.
    • Return the last element from the array without removing it from the queue.

  4. Empty Operation:

    • Check if the queue is empty.

Time and Space Complexity

  • Push Operation:

    • Time Complexity: (O(1)) - Adding an element to the queue is a constant time operation.
    • Space Complexity: (O(1)) - No additional space is used apart from the input element.

  • Pop Operation:

    • Time Complexity: (O(n)) - We need to transfer all elements to an array and back to the queue.
    • Space Complexity: (O(n)) - An array of size (n) is used to store the elements temporarily.

  • Top Operation:

    • Time Complexity: (O(n)) - Similar to pop, we transfer all elements to an array and back.
    • Space Complexity: (O(n)) - An array of size (n) is used to store the elements temporarily.

  • Empty Operation:

    • Time Complexity: (O(1)) - Checking if the queue is empty is a constant time operation.
    • Space Complexity: (O(1)) - No additional space is used.

The Code

Here’s the Java code for our MyStack class:

class MyStack {
    Queue<Integer> queue = new LinkedList<>();
    public MyStack() {
       
    }
   
    public void push(int x) {
        queue.add(x);
    }
   
    public int pop() {
        int[] arr = new int[queue.size()];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = queue.poll();
        }
        for (int i = 0; i < arr.length - 1; i++) {
            queue.add(arr[i]);
        }
        return arr[arr.length - 1];
    }
   
    public int top() {
        int[] arr = new int[queue.size()];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = queue.poll();
        }
        for (int i = 0; i < arr.length; i++) {
            queue.add(arr[i]);
        }
        return arr[arr.length - 1];
    }
   
    public boolean empty() {
        if (queue.size() <= 0) {
            return true;
        }
        return false;
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

Conclusion

Implementing a stack using a queue is a great exercise to understand the underlying principles of data structures. It shows how we can manipulate one data structure to mimic the behavior of another. This kind of problem-solving is essential for developing a deeper understanding of algorithms and data structures.

Comments

Post a Comment

Popular posts from this blog

3Sum Closest: O(n²) Two-Pointer Magic 🚀 leetcode: 16

Three Sum Closest - LeetCode Solution In this blog post, we'll dive into the Three Sum Closest problem, a popular coding challenge on LeetCode. We'll explore the intuition behind the solution, discuss the approach, analyze the complexity, and provide a detailed explanation of the code. Additionally, I'll share my LeetCode solution link for further reference. Problem Statement Given an integer array nums of length n and an integer target , find three integers in nums such that the sum is closest to target . Return the sum of the three integers. You may assume that each input would have exactly one solution. Intuition The problem requires finding three numbers in the array whose sum is as close as possible to the target. To efficiently find such a triplet, we can use a combination of sorting and the two-pointer technique . Sorting : First, sort the array. This allows us to use the two-po...
Read more

Kadane's Algorithm: Maximum Subarray Problem - LeetCode(53) Solution

Maximum Subarray Problem - LeetCode Solution Maximum Subarray Problem - LeetCode Solution Problem Statement Given an integer array nums , find the contiguous subarray (containing at least one number) that has the largest sum and return its sum. Intuition The problem requires finding the contiguous subarray with the maximum sum. A brute force approach would involve checking all subarrays, but this would be inefficient. Instead, we use Kadane's Algorithm , which efficiently finds the maximum sum subarray in O(n) time. Approach Initialize two variables: total (running sum) and maxi (maximum sum encountered so far). Iterate through the array: Add the current element to total . Update maxi with the maximum of maxi and total . If total becomes negative, reset it to zero. Return maxi as the maximum sub...
Read more

LeetCode Problem: Implement pow(x, n) leetcode:- 50

Understanding the Fast Exponentiation Algorithm: Exponentiation by Squaring In this blog post, we will explore the implementation of the myPow function, a common problem found on LeetCode. The goal of this problem is to compute \(x^n\) efficiently, even when \(n\) is a very large number. Instead of using a naive approach, we employ a method called Exponentiation by Squaring to significantly reduce the number of multiplications required. Problem Overview Given a floating-point number x and an integer n , our task is to implement a function that computes \(x^n\). A straightforward solution might involve multiplying x by itself n times, but this approach is too slow when n is large. Intuition Behind Exponentiation by Squaring The main idea is to reduce the problem size by halving the exponent at each recursive step. Consider the following: If n is even, then: \(x^n = x^{...
Read more