Implement Stack using Queues, Implement Queue using Stacks, Add and Search Word - Data structure design

Implement Stack using Queues

Implement the following operations of a stack using queues.
push(x) — Push element x onto stack.
pop() — Removes the element on top of the stack.
top() — Get the top element.
empty() — Return whether the stack is empty.
Notes:
You must use only standard operations of a queue — which means only push to back, peek/pop from front, size, and is empty operations are valid.
Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).
Update (2015-06-11):
The class name of the Java function had been updated to MyStack instead of Stack.

Three Solutions

• O(1) push, O(n) top, O(n) pop - use two Queues: always push to p1; when pop copy first n-1 items to p2, poll nth item from p1, switch p1 p2; when top, copy first n-1 to p2, peek q1, switch and return
• O(n) push, O(1) top, O(1) pop - use two Queues: always keep pushed item at first in p2, then add p1 to p2
• O(1) push, O(n) top, O(n) pop - use one Queue: push to last of list; when pop offer n-1 item polled to the end of list; when top do the same, return peeked item, then offer the first item to list

  	Deque<Integer> q = new ArrayDeque<Integer>();

// Push element x onto stack.
   public void push(int x) {
       q.add(x);
   }

   // Removes the element on top of the stack.
   public void pop() {
       int i=0;
       while(i<q.size()-1){
           q.offer(q.poll());
           i++;
       }
       q.poll();
       return;
   }

   // Get the top element.
   public int top() {
       int i=0;
       while(i<q.size()-1){
           q.offer(q.poll());
           i++;
       }
       int x = q.peek();
       q.offer(q.poll());
       return x;
   }

   // Return whether the stack is empty.
   public boolean empty() {
       return q.isEmpty();
   }

---

Implement Queue using Stacks

Implement the following operations of a queue using stacks.
push(x) — Push element x to the back of queue.
pop() — Removes the element from in front of queue.
peek() — Get the front element.
empty() — Return whether the queue is empty.
Notes:
You must use only standard operations of a stack — which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

Solution

• Simple two stack solution…

Stack<Integer> stk = new Stack<Integer>();
	Stack<Integer> stk2 = new Stack<Integer>();
	// Push element x to the back of queue.
	public void push(int x) {
		stk.push(x);
	}

	// Removes the element from in front of queue.
	public void pop() {
		int i = 0, n=stk.size();
		while(i<n-1){
			stk2.push(stk.pop());
			i++;
		}
		stk.pop();
		i=0;
		while(i<n-1){
		    stk.push(stk2.pop());
		    i++;
		}
	}

	// Get the front element.
	public int peek() {
		int i = 0, n=stk.size();
		while(i<n-1){
			stk2.push(stk.pop());
			i++;
		}
		int x = stk.peek();
		i=0;
		while(i<n-1){
		    stk.push(stk2.pop());
		    i++;
		}
		return x;
	}

	// Return whether the queue is empty.
	public boolean empty() {
		return stk.isEmpty();   
	}

One stack Solution

• (Function Call Stack)

Stack<Integer> stk = new Stack<Integer>();
// Push element x to the back of queue.
public void push(int x) {
	stk.push(x);
}

// Removes the element from in front of queue.
public void pop() {
       this.remove();
}

public int remove(){
    int top = stk.pop();
       if(stk.isEmpty()){
           return top;
       }
       else{
           int res = this.remove();
           stk.push(top);
           return res;
       }
}

// Get the front element.
public int peek() {
       int top = stk.pop();
       if(stk.isEmpty()){
           stk.push(top);
           return top;
       }
       else{
           int res = this.peek();
           stk.push(top);
           return res;
       }
}

// Return whether the queue is empty.
public boolean empty() {
	return stk.isEmpty();   
}

---

Add and Search Word - Data structure design

Design a data structure that supports the following two operations:
void addWord(word)
bool search(word)
search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.
For example:
addWord(“bad”)
addWord(“dad”)
addWord(“mad”)
search(“pad”) -> false
search(“bad”) -> true
search(“.ad”) -> true
search(“b..”) -> true
Note:
You may assume that all words are consist of lowercase letters a-z.
click to show hint.
You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.

Solution

• One solution would be to keep a Map of word length and list of words, this way when we search on a string s, we need to compare the string with each string in the list of same length
• Use Trie, when

private class TrieNode{
       TrieNode[] child = new TrieNode[26];
       boolean isWord;
   }
   
   TrieNode root = new TrieNode();
   // Adds a word into the data structure.
   public void addWord(String word) {
       addWord(word.toCharArray(), 0, root);
   }
   
   public void addWord(char[] s, int i, TrieNode root){
       if(root.child[s[i] - 'a']==null){
           root.child[s[i] - 'a'] = new TrieNode();
       }
       if((s.length-1) == i){
           root.child[s[i] - 'a'].isWord = true; //set leaf to isword
           return;
       }
       addWord(s, i+1, root.child[s[i] - 'a']);
   }

   // Returns if the word is in the data structure. A word could
   // contain the dot character '.' to represent any one letter.
   public boolean search(String word) {
       return searchWord(word.toCharArray(), 0, root);
   }
   
   public boolean searchWord(char[] s, int i, TrieNode root){
       if(i == s.length){ //when reached input length, return if it's word
           return root.isWord;
       }
       char cur = s[i];
       if(cur == '.'){
           for(int p=0; p<root.child.length; p++){
               if(root.child[p] != null) 
               	if(searchWord(s, i+1, root.child[p]))
               		return true;
           }
           return false;
       }
       if(root.child[cur-'a'] == null) 
           return false;
       return searchWord(s, i+1, root.child[cur-'a']);
   }