Iterators - Allowing iteration over data structures (in java)

Many times we need to iterate over the data structures. But should we allow our clients to know the internal details of the data-structure like whether it is using array or linked list and then iterate themselves. Here's where java gives us the power called iterators which allows us to iterate over data structure. Design Challenge Consider the stack data structure and we want to support iteration over it on client side. Step 1 - Make your stack ADT implement Iterable interface. What is Iterable? has a method that returns an Iterator. public...

Read More

Generic data structures in java

Suppose we have a stack of string, but later we want to use it for integers. We have to re-write the code again and again for every data type. So how can we solve this. Attempt 1 - Creating the stack for every data type, which is very exhaustive and needs code changes again. Attempt 2 - Implement a stack using Object class. Example Downside - Discover type mismatch errors at run time Casting has to be done at client side Code looks ugly because of so many castings Attempt 3 - Java generic...

Read More

Evaluating postfix expression using stack

We have seen the conversion of infix to postfix expression here. Now lets  see how to evaluate it. Algorithm Scan input expression from left to right If scanned input is an operand, push it into the stack If scanned input is an operator, pop out two values from stack. Then, perform operation between popped values and then push back the result into the stack. Repeat above two steps till all the characters are scanned. After all characters are scanned, there will be only one element in the stack, and this is the result of given expression. Note...

Read More

Converting an Infix Expression to Postfix expression using a stack

Pre-requisite - What is infix, postfix and prefix? Infix, Postfix and Prefix notations are three different but equivalent ways of writing expressions.  Postfix is also known as Reverse Polish Notation or RPN , and prefix expression is also known as Polish notation. Infix - Operators are written in-between their operands. eg.  A+B Postfix -  Operators are written after their operands.      eg.  AB+...

Read More

Checking whether the paranthesis are balanced in the expression

Problem  Checking whether the paranthesis are balanced in the expression Solution Method 1 - Using stacks Stacks can be used to compare the paranthesis.  Whenever we find the opening paranthesis we push it in the stack, and whenever we find closing paranthesis, we pop it out from stack. When the expression finishes and stack is not empty, then it means that paranthesis are not balanced otherwise they are. Example 1 Consider the following...

Read More

Resizing Array implementation of stack

We have already seen the array implementation of stack, which had one limitation of what happens if data size is bigger than array size, i.e. over flow occurs. To solve this we have to grow our array. But how? Growing the Array Approach 1 - Repeated Doubling i.e. Doubling the array every time it is full We can grow the array by doubling it size, and copying the elements in older array to newer one. Here is how: public class ResizingArrayStackOfString { String[] s; int N; public ResizingArrayStackOfString() { s = new String[1]; } public...

Read More

Introduction of Array

This is the basic or simplest type of data structure. An array can be defined as, a list of a finite number "n" of similar data elements referenced respectively by a set of n consecutive numbers, usually 1, 2, 3, ..., n. If A is chosen for the name of some array, then the elements of A are denoted as, a1, a2, a3, a4, ..., an OR  A(1), A(2), A(3), A(4), ..., A(n) OR  A[1], A[2], A[3], A[4], ..., A[n] Regardless of the notation, the number K in A[K] is called a subscript and A[K] is called a subscripted variables. There are some important...

Read More