A queue can be implemented using two stacks.
Let queue to be implemented be q and stacks used to implement q be stack1 and stack2.
q can be implemented in two ways:
Method 1 (By making enQueue operation costly)
This method makes sure that newly entered element is always at the top of stack 1,
so that deQueue operation just pops from stack1. To put the element at top of stack1, stack2 is used.
enQueue(q, x)
1) While stack1 is not empty, push everything from satck1 to stack2.
2) Push x to stack1 (assuming size of stacks is unlimited).
3) Push everything back to stack1.
deQueue(q)
1) If stack1 is empty then error
2) Pop an item from stack1 and return it
Method 2 (By making deQueue operation costly)
In this method, in en-queue operation, the new element is entered at the top of stack1.
In de-queue operation, if stack2 is empty then all the elements are moved to stack2 and finally top of stack2 is returned.
enQueue(q, x)
1) Push x to stack1 (assuming size of stacks is unlimited).
deQueue(q)
1) If both stacks are empty then error.
2) If stack2 is empty
While stack1 is not empty, push everything from satck1 to stack2.
3) Pop the element from stack2 and return it.
Method 2 is definitely better than method 1. Method 1 moves all the elements twice in enQueue operation,
while method 2 (in deQueue operation) moves the elements once and moves elements only if stack2 empty.
Queue can also be implemented using one user stack and one Function Call Stack.
Below is modified Method 2 where recursion is used to implement queue using only one user defined stack.
enQueue(x)
1) Push x to stack1.
deQueue:
1) If stack1 is empty then error.
2) If stack1 has only one element then return it.
3) Recursively pop everything from the stack1, store the popped item
in a variable res, push the res back to stack1 and return res
The step 3 makes sure that the last popped item is always returned and since the recursion stops when there is only one item in stack1 (step 2), we get the last element of stack1 in dequeue() and all other items are pushed back in step 3.
Saturday, September 3, 2011
Implement Queue using Stacks
Levenshtein Distance
int LevenshteinDistance(char s[1..m], char t[1..n])
{
// for all i and j, d[i,j] will hold the Levenshtein distance between
// the first i characters of s and the first j characters of t;
// note that d has (m+1)x(n+1) values
declare int d[0..m, 0..n]
for i from 0 to m
d[i, 0] := i // the distance of any first string to an empty second string
for j from 0 to n
d[0, j] := j // the distance of any second string to an empty first string
for j from 1 to n
{
for i from 1 to m
{
if s[i] = t[j] then
d[i, j] := d[i-1, j-1] // no operation required
else
d[i, j] := minimum
(
d[i-1, j] + 1, // a deletion
d[i, j-1] + 1, // an insertion
d[i-1, j-1] + 1 // a substitution
)
}
}
return d[m,n]
}
|
|
Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted
Example : 10,12, 20,30, 25,40,32,31,35,50,60
1) Find the candidate unsorted subarray
a) Scan from left to right and find the first element which is greater than the next element.Let s be the index of such an element. In the above example 1, s is 3 (index of 30).
b) Scan from right to left and find the first element (first in right to left order) which is smaller than the next element (next in right to left order).Let e be the index of such an element.In the above example 1, e is 7 (index of 31).
2) Check whether sorting the candidate unsorted subarray makes the complete array sorted or not. If not, then include more elements in the subarray.
a) Find the minimum and maximum values in arr[s..e]. Let minimum and maximum values be min and max. min and max for [30, 25, 40, 32, 31] are 25 and 40 respectively.
b) Find the first element (if there is any) in arr[0..s-1] which is greater than min, change s to index of this element.There is no such element in above example 1.
c) Find first element (if there is any) in arr[e+1..n-1] which is smaller than max, change e to index of this element.In the above example 1,e is changed to 8 (index of 35)
3) Print s and e.
Find the pair from an sorted array whose difference is x
Here is an inplace solution with O(n) complexity.
i=0,j=1;
while((i!=n-1) or j!=n)
{
/*compare difference of a[j] and a[i]*/
if( (a[j]-[a[i]])>x ) {
i++;j++;
}
else if( (a[j]-a[i]) {
j++;
}
else
{
/*SOLUTION*/
return;
}
}
Find 10 maximum integer out of 1 million integers
You Have File of Containing 1 Million Integers You need To Find 10 Maximum Integer Out of Them.How You Will Do That. What is Time & space Complexity of Algorithm that you will use then optimize the solution.. Constraints- U can't Store Whole File in memory @ one time e.g. if u will do that gigabyte of memory may be required so that should be avoided. Answer: Using the first 10 numbers, build a max heap. Then add each number into the 11th array position (always the 11th position) and perform the up-heap operation. At the end of the input, discard the 11th number in the heap. The remaining numbers will be the 10 maximum. O(n log k) where n = the number of items in the list and k = the number of maximum items you want.
Find whether given tree is a subtree or not
Given two binary trees T1 and T2 which store character data, duplicates allowed. You have to devise an algorithm to decide whether the T2 is a subtree of T1. T1 has millions of nodes and T2 has hundreds of nodes.
Pseudo code :
check( node t1 , node t2 )
{
if ( t1->data == t2->data)
{
return check( t1->left , t2->left ) && check(t1->right, t2->right) ;
}
else
{
return check(t1->left , t2) || check(t1->right , t2);
}
}
Time complexity :O(n) because each node in T1 needs to be visited once.
Given an array of integers, each element represents the max number of jumps can make forward. What is the minimum number of element selections to reach the end of the array
Given an array of integers, each element represents the max number of jumps can make forward.
What is the minimum number of element selections to reach the end of the array (starting from the first element) ?
Example: arr = 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9
Here the min # of selections is : 3
with the sequence : 1-> 3 -> 8 ->9
First element is 1, so can only go to 3.
Second element is 3, so can make at most 3 jumps: eg to 5 or 8 or 9.
If an element is 0, then cannot make any jumps
Implementation : Using Dynamic programming -
int find_min_steps(int arr[], int n)
{
// min_steps_dp[i] is an array which
// indicate minimum jumps required to reach i.
int min_steps_dp[20];
int i, temp, next_vacant;
// next_vacant : Is the index in the array whose min_steps needs to be updated
// in the next iteration.
next_vacant = 1;
for(i=0;i= n)
{
min_steps_dp[n-1] = min(min_steps_dp[n-1],min_steps_dp[i] +1);
}
else
{
min_steps_dp[temp] = min(min_steps_dp[temp],min_steps_dp[i]+1);
}
if(temp>next_vacant)
{
for(;next_vacant<temp;next_vacant++)
{
// this loop executes only ONCE for each element in the array, so over the
// course of execution, is an O(n) loop only.
min_steps_dp[next_vacant] =min(min_steps_dp[next_vacant],min_steps_dp[temp]);
}
}
}
for(i=0;i<n;i++)
{
printf("%d ",min_steps_dp[i]);
}
return min_steps_dp[n-1];
}
main()
{
int arr[] = {1,3,5,8,9,2,6,7,6,8,9};
int len;
len = sizeof(arr)/sizeof(arr[0]);
printf("\n MIN steps : %d\n",find_min_steps(arr,len));
}
Subscribe to:
Posts (Atom)