Thursday, 3 May 2018

Algorithms | Implement a stack using single queue

Given queue data structure and we need to implement a stack using only given queue data structure. The assumption is that that we can find the size of the queue at any point.

The idea is to keep newly inserted element always at the front, keeping the order of previous elements same. Below are complete steps.

// e is the element to be pushed and s is stack
push(s, e)
  1) Enqueue e to q
  2) One by one Dequeue s items from queue and enqueue them except ‘e’.
 
// Removes an item from the stack
pop(s)
  1) Dequeue an item from q

package com.stackqueue;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Implement stack using <B>only</B> given queue data structure.
 *
 *
 * We need to focus on the insertion logic of the element.
 * Newly inserted element always at front, keeping order of previous elements same.
 *
 * Steps# (x is the element to be pushed and s is stack)
 *      push(s, x)
 *          Let size of q be s.
 *          1) Enqueue x to q
 *          2) One by one Dequeue s items from queue and enqueue them.
 *         
 *      pop(s) : Removes an item from stack
 *          1) Dequeue an item from q
 *
 * @link https://www.geeksforgeeks.org/implement-a-stack-using-single-queue/
 *
 * @author rajesh dixit
 * @since May 2, 2018 4:30:58 PM
 */
public class ImplementStackUsingSingleQueue {

    private static class Stack<E> {

        /** Queue, which is used to store the stack element. */
        Queue<E> queue = new LinkedList<>();

        /**
         * Returning the peek element of the Stack.
         * @return
         */
        public E peek() {
            return queue.peek();
        }

        /**
         * Returning the front of Queue.
         *
         * @return top element of the Stack.
         */
        public E poll() {
            return queue.poll();
        }

        /**
         * Adding element at rear and to achieve LIFO, polling front from queue and adding it to rear.
         *
         * @param value
         * @return true on add of element
         */
        public boolean push(E value) {
            boolean result = queue.add(value);
            for (int i = 0; i < queue.size() - 1; i++) {
                E element = queue.poll();
                queue.add(element);
            }
            return result;
        }
    }

    /**
     * Driver method
     *
     * @param args
     */
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

        stack.push(1);
        stack.push(2);
        int e1 = stack.poll();
        System.out.println(e1);

        stack.push(4);
        e1 = stack.peek();
        System.out.println(e1);
    }
}


Algorithms | Reverse actual bits of the given number

Given a non-negative integer N, reverse the bits of N and print the number obtained after reversing the bits.

Note: actual binary representation of the number is being considered for reversing the bits, no leading 0’s are being considered.

Example
Input: 11
Output: 13

(11)10 = (1011)2.
Reversing the bits:
(1101)2 = (13)10.

Input: 12
Output: 3

(12)10 = (1100)2.
Reversing the bits:
(0011)2 = (3)10.


package com.microsoft.set166;
/**
 * Reverse actual bits of the given non-negative integer n.
 *
 * @author rajesh dixit
 * @since May 2, 2018 12:55:36 PM
 */
public class ReverseBits {

    /**
     * Method reverse the Bits to form a new number.
     *
     * @param value
     * @return reversed number
     */
    private static int getReverseBitNumber(int value) {
        int rev = 0;
        while (value > 0) {
            int lastBit = value & 1;

            rev = rev << 1;

            rev = rev | lastBit;

            value = value >> 1;
        }
        return rev;
    }
   
    /**
     * Driver method
     *
     * @param args
     */
    public static void main(String[] args) {

        int value = 14;
        int revValue = getReverseBitNumber(value);

        System.out.println(revValue);
    }
}
Related Posts Plugin for WordPress, Blogger...