Queue using Stack in Java

A Queue can constructed with its underlying data structure being a stack. Typically, we will need two Stacks one for enqueue and the other for dequeue.

During every enqueue() operation over a queue, we will keep pushing value to a first stack, lets say stack1.

During every dequeue() operation, we will have to simply pop an element from stack2 if stack2 is not empty. If stack2 is empty, we will need to pop all elements from stack1 one by one and push it to stack2. And then pop an element from stack2.

Take for example, I am inserting elements from 1 to 6 to a queue. This is how the following queue and the corresponding stack will look like,

Then trying a dequeue() operation will try to immediately pop values from stack 2.

So, it will pop all values from stack1 and push them to stack2 as follows,

Now the dequeue() operation shall be performed with ease since stack2 is not empty.

Finally, more enqueue will add or keep pushing values to the stack.

Following is the Java code. Note, I have not comprehensively covered the entire methods in a Queue, but this should be well more than enough.



And a test class for this with output


Cheers!
Braga

TRIE data structure Part 6 : A Sample UI

• 1
• 2
• 3
• 4
• 5
• 6
• 7

Lets have a look at a sample application in Swing. We load the TRIE data structure using a dictionary word list. And using the application we can perform a search. This application is a very much prototypical just to check the insert() and search() operations.

Input file : words.txt

Sample Application

There are two possible outcomes to our search criteria, one true and another false. The following is the dialog shown when a word "article" is entered.

And when a word something like "dasdsa" is entered the following dialog is shown.

The Java code for the Trie Loader,

package dsa.tries;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;

public class TrieLoader {
 
 public static Trie trieDSA;

 public static void main(String[] args) {
  TrieLoader trieLoader = new TrieLoader();
  trieLoader.load();
  new TrieTestFrame();
 }
 
 public void load(){
  trieDSA = new Trie();
  BufferedReader br = null;
  try {
   br = new BufferedReader(new FileReader(new File("src/properties/words.txt")));
   String eachLine = null;
   while((eachLine=br.readLine())!=null){
    trieDSA.insert(eachLine);
   }
  } catch (Exception e) {
   e.printStackTrace();
  } finally{
   if(br!=null){
    try {
     br.close();
    } catch (IOException e) {
     e.printStackTrace();
    }
   }
  }
 }
}

The TrieTestFrame,

package dsa.tries;

import java.awt.Dimension;
import java.awt.Toolkit;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JOptionPane;
import javax.swing.JPanel;
import javax.swing.JTextField;

public class TrieTestFrame extends JFrame {

 private static final long serialVersionUID = 1L;
 
 private JPanel basePanel = new JPanel();
 private JTextField textField = new JTextField(20);
 private JButton button = new JButton("Check");

 public TrieTestFrame(){
  designUI();
 }
 
 private void designUI(){
  this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
  this.setTitle("TRIE Test");
  
  button.addActionListener(new ActionListener() {
   @Override
   public void actionPerformed(ActionEvent e) {
    if(TrieLoader.trieDSA.search(textField.getText())){
     JOptionPane.showMessageDialog(basePanel, "The word you entered exist!!");
    }else{
     JOptionPane.showMessageDialog(basePanel, "The word you entered does not exist!!","Error",JOptionPane.ERROR_MESSAGE);
    }
   }
  });
  
  basePanel.add(textField);
  basePanel.add(button);
  
  add(basePanel);
  
  this.setSize(400,100);
  
  Toolkit tk = Toolkit.getDefaultToolkit();
     Dimension screenSize = tk.getScreenSize();
     int screenHeight = screenSize.height;
     int screenWidth = screenSize.width;
     setLocation(screenWidth / 2 - 200, screenHeight / 2 - 50);
  
  this.setVisible(true);
 }
}

For the Node and Trie class please click here.

Cheers,
Bragaadeesh.

TRIE data structure Part 5 : Complexity Analysis

• 1
• 2
• 3
• 4
• 5
• 6
• 7

Now that we've seen the basic operations on how to work with a TRIE, we shall now see the space and time complexities in order to get a real feel of how good a TRIE data structure is. Lets take the two important operations INSERT and SEARCH to measure the complexity.

INSERT operation first. Lets always take into account the worst case timing first and later convince ourselves of the practical timings. For every Node in the TRIE we had something called as Collection where the Collection can be either a Set or a List. If we choose Set, the order of whatever operation we perform over that will be in O(1) time, whereas if we use a LinkedList the number of comparisons at worst will be 26 (the number of alphabets). So for moving from one node to another, there will be at least 26 comparisons will be required at each step. 

Having these in mind, for inserting a word of length 'k' we need (k * 26) comparisons. By Applying the Big O notation it becomes O(k) which will be again O(1). Thus insert operations are performed in constant time irrespective of the length of the input string (this might look lik an understatement, but if we make the length of the input string a worst case maximum, this sentence holds true).

Same holds true for the search operation as well. The search operation exactly performs the way the insert does and its order is O(k*26) = O(1).

TRIE data structure Part 3 : The INSERT Algorithm

• 1
• 2
• 3
• 4
• 5
• 6
• 7

In this section we shall see how the insert() method on the TRIE data structure works. We shall take a specific case and analyze it with pictorial representation.

Before we begin, assume we already have an existing TRIE as shown below.

Lets see the steps on how to insert a word "bate". Any insertion would ideally be following the below algorithm.

1. If the input string length is zero, then set the marker for the root node to be true.
2. If the input string length is greater than zero, repeat steps 3 and 4 for each character
3. If the character is present in the child node of the current node, set the current node point to the child node.
4. If the character is not present in the child node, then insert a new node and set the current node to that newly inserted node.
5. Set the marker flag to true when the end character is reached.

Now if you go through the already written code for this, you can have a better understanding by comparing it with the above algorithm.

public void insert(String s){
  Node current = root; 
  if(s.length()==0) //For an empty character
   current.marker=true;
  for(int i=0;i<s.length();i++){
   Node child = current.subNode(s.charAt(i));
   if(child!=null){ 
    current = child;
   }
   else{
    current.child.add(new Node(s.charAt(i)));
    current = current.subNode(s.charAt(i));
   }
   // Set marker to indicate end of the word
   if(i==s.length()-1)
    current.marker = true;
  } 
 } 

Now lets see how the word "bate" is getting inserted. Since the word "bate" is having length greater than zero, we can start inspecting each word.

• See whether "b" is present in the current node's children (which is root). Yes its present, so set the current node to the child node which is having the character "b".
• See whether "a" is present in the current node's children. Yes its present, so set the current node to the child node which is having the character "a".
• See whether "t" is present in the current node's children. Yes its present, so set the current node to the child node which is having the character "t".
• See whether "e" is present in the current node's children. No, its not present, so create a new node with character set to "e". Since "e" is the end of the word, set the marker flag to true.

The above picture shows how the word "bate" is inserted into the existing TRIE data structure. This example clearly shows how the insertion in a TRIE happens.
We shall take a look on the Search operation in the next part.

Cheers,
Bragaadeesh.

TRIE data structure Part 1: The TRIE ADT in Java

• 1
• 2
• 3
• 4
• 5
• 6
• 7

TRIE is an interesting data-structure used mainly for manipulating with Words in a language. This word is got from the word retrieve. TRIE (pronounced as 'try') has a wide variety of applications in

• Spell checking
• Data compression
• Computational biology
• Routing table for IP addresses
• Storing/Querying XML documents etc.,

We shall see how to construct a basic TRIE data structure in Java.

The main abstract methods of the TRIE ADT are,

public void insert(String s);
public boolean search(String s);

In this data-structure, each node holds a character instead of a String. Each node has something called as 'marker' to mark the end of a word. And each node has a Collection of child nodes. This Collection can be either a Set or a List based on the speed vs space criterion.

The basic element - Node of a TRIE data structure looks like this,

char content;
boolean marker;
Collection<Node> child;

A TRIE tree would typically look like the following

The above TRIE is constructed by inserting the words ball, bat, doll, dork, do, dorm, send, sense. The markers are denoted on the Node using a red star(*). We shall look into more about the TRIE data structure in depth in the next post.

Traversals in a binary search tree in Java

Now that we have seen how a binary tree is structured and doing a search operation over the same, lets look at how we can traverse over that data structure. There are three types of traversals that can be done.

1. In-order traversal
2. Pre-order traversal
3. Post-order traversal

In-order traversal follows the route VISIT LEFT / VISIT ROOT / VISIT RIGHT. For a given binary tree, first visit the left most node and if no left node exists, visit the root and then visit the right. By this fashion traversal can be done. As a matter of fact, a simple In-order traversal in a binary search tree would give the sorted result! How cool is that!?

If you take a look at the above picture (yes, it looks a bit crowded, but you can track the numbers from 1 through twenty and the green ones are the values that we take), we start the process from the root and end up in the root. First search for the left most node. If there is none available take the immediate root and apply the same algorithm to the current node's right node. What i say may be a bit confusing but follow the numbers, you'l know.

Pre-order traversal follows the route VISIT ROOT / VISIT LEFT / VISIT RIGHT and the Post-order traversal follows the VISIT LEFT, VISIT RIGHT, VISIT ROOT.

For the above given example, the sequence that we get for various traversals is listed in the table below. You can cross-check it for yourself.

Order	Sequence
In-order	9, 12, 14, 17, 19, 23, 50, 54, 67, 72, 76
Pre-order	50, 17, 9, 14, 12, 23, 19, 76, 54, 72, 67
Post-order	12, 14, 9, 19, 23, 17, 67, 72, 54, 76, 50

In order traversal's application is clearly visible in this example (it gives a sorted list). Pre and post order traversals too have some powerful applications which we will look in the following posts.

Cheers,
Bragaadeesh.