Array Implementation of Queue (Fixed size)

github:arrayQueue.java

Purpose:

reuse a fixed size array. —-> Tracking 2 variables frontIndex for deletion and rearIndex for insertion.

CheckPoint:

  1. array size > 0.
  2. isEmpty()
  3. Check rearIndex == frontIndex.
  4. Enqueue –> queue is full.
  5. Dequeue –> queue is empty.

Complexity Analysis:

Time complexity :
enqueue: O(1)
assign the value to array[rearIndex]

dequeue: O(1)
move frontIndex to next index.

Space complexity : O(n)

 

The result:

Screen Shot 2017-04-12 at 9.48.43 PM

Exception checking:

Screen Shot 2017-04-12 at 9.56.48 PMScreen Shot 2017-04-12 at 9.57.41 PMScreen Shot 2017-04-12 at 9.58.28 PM

 

Implement Queue using Stacks

github: ImplementQueueusingStacks.java

Using 2 stacks- s1 and s2 to implement a queue.

Purpose: keep the input on the bottom of s1.

The idea is that when an input comes, we push the input to s1, BUT only if the s1 is empty. If s1 is not empty then we pop out all element from s1 and push into s2,
so that we always keep the input on the bottom of s1.

Complexity Analysis:

Time complexity :
PUSH: O(n)
Since we need pop out all elements in s1 and push in that elements in s2 before we push the input in the s1 also pop out s2 and push back s1. so it should be O(n).
POP: O(1)
We only pop out the top of s1. So it is O(1).

Space complexity :
PUSH: O(n). We need n space to store the coming queue elements.
POP: O(1). We only keep one element- the top of s1 which pop out from s1. So it is O(1).

void push(int x):
check
a while loop , if s1 is not empty,
pop all elements in the s1 and also push the elements to s2
so s2 contains the reverse of s1.

then push x to s1

a while loop, if s2 is not empty,
pop all elements in the s2 and also push the elements to s1

assign x to the integer-front

int pop():
assign the element from pop s1 to x
assign s1.peek() to the integer-front
return x.

int peek():
return front.

boolean empty():
return s1.empty();

Palindrome Checker

Screen Shot 2017-03-26 at 10.53.54 PM

github: Palindrome.java

A few good ways to remove space from a string.

Method 1

private static String removeSpace(String aword) {
     StringBuilder buffer = new StringBuilder();
        for (int i = 0; i < aword.length(); i++)   {
         if (aword.charAt(i) != ' ')) {
             buffer.append(aword.charAt(i));
         }
     }
     return buffer.toString();
}

Method 2

        //Removing all white spaces from s1 and s2
        String copyOfs1 = s1.replaceAll("\\s", "");
        String copyOfs2 = s2.replaceAll("\\s", "");