Stack & Queue Problems

0.Simplify Path
http://www.programcreek.com/2014/04/leetcode-simplify-path-java/

1.Sliding Window Maximum
Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.
Examples:
Input :
arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}
k = 3
Output :
3 3 4 5 5 5 6
C++ Implementation:
http://www.geeksforgeeks.org/maximum-of-all-subarrays-of-size-k/
http://articles.leetcode.com/sliding-window-maximum/
Java Implementation:

http://www.programcreek.com/2014/05/leetcode-sliding-window-maximum-java/

2.Moving Average from Data Stream in a sliding window

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

http://www.programcreek.com/2014/05/leetcode-moving-average-from-data-stream-java/

Moving Average from Data stream:

Given a stream of numbers, print average (or mean) of the stream at every point. For example, let us consider the stream as 10, 20, 30, 40, 50, 60, …

Average of 1 numbers is 10.00
  Average of 2 numbers is 15.00
  Average of 3 numbers is 20.00
  Average of 4 numbers is 25.00
  Average of 5 numbers is 30.00
  Average of 6 numbers is 35.00
  .................. 

Strategy:

To print mean of a stream, we need to find out how to find average when a new 

number is being added to the stream. To do this, all we need is count of numbers 

seen so far in the stream, previous average and new number. Let n be the count, 

prev_avg be the previous average and x be the new number being added. 

The average after including x number can be written as (prev_avg*n + x)/(n+1). 

Code:

#include <stdio.h>
 
// Returns the new average after including x
float getAvg(float prev_avg, int x, int n)
{
    return (prev_avg*n + x)/(n+1);
}
 
// Prints average of a stream of numbers
void streamAvg(float arr[], int n)
{
   float avg = 0;
   for(int i = 0; i < n; i++)
   {
       avg  = getAvg(avg, arr[i], i);
       printf("Average of %d numbers is %f \n", i+1, avg);
   }
   return;
}

int main()
{
    float arr[] = {10, 20, 30, 40, 50, 60};
    int n = sizeof(arr)/sizeof(arr[0]);
    streamAvg(arr, n);
    getchar();
    return 0;
}

The above function getAvg() can be optimized using following changes. We
can avoid the use of prev_avg and number of elements by using static 
variables (Assuming that only this function is called for average of 
stream). Following is the oprimnized version.

Revised Code:

#include <stdio.h>
 
// Returns the new average after including x
float getAvg (int x)
{
    static int sum, n;
 
    sum += x;
    return (((float)sum)/++n);
}
 
// Prints average of a stream of numbers
void streamAvg(float arr[], int n)
{
   float avg = 0;
   for(int i = 0; i < n; i++)
   {
       avg  = getAvg(arr[i]);
       printf("Average of %d numbers is %f \n", i+1, avg);
   }
   return;
}

int main()
{
    float arr[] = {10, 20, 30, 40, 50, 60};
    int n = sizeof(arr)/sizeof(arr[0]);
    streamAvg(arr, n);
    getchar();
    return 0;
}

3. Next higher element for each element in an array.
For e.g. if array is 1 2 3 4 5 8 6
o/p should be
(element) (next higher element)
1 2
2 3
3 4
4 5
5 8
8 nothing
6 nothing

Or
You are given an unsorted array A of n elements, now construct an array B for which B[i] = A[j] where j is the least number such that A[j] > A[i] and j>i if such a j does not exist B[i] = -1 Eg:

A={1,3,5,7,6,4,8}
B = {3 5 7 8 8 8 -1}

Approach:

While iterating over the array if the element is smaller than stack top, push it to stack along with index.if the element is larger than stack top, pop till current element is smaller than stack top and for all the popped indices store the current element.
Code:

#include<stdio.h>
#include<stdlib.h>
#define STACKSIZE 100

struct stack
{
    int top;
    int items[STACKSIZE];
};

void push(struct stack *ps, int x)
{
    if (ps->top == STACKSIZE-1)
    {
        printf("Error: stack overflow\n");
        getchar();
        exit(0);
    }
    else
    {
        ps->top += 1;
       ps->items[ps->top] = x;
    }
}

bool isEmpty(struct stack *ps)
{
    return (ps->top == -1)? true : false;
}

int pop(struct stack *ps)
{
    int temp;
    if (ps->top == -1)
    {
        printf("Error: stack underflow \n");
        getchar();
        exit(0);
    }
    else
    {
        temp = ps->items[ps->top];
        ps->top -= 1;
        return temp;
    }
}

void printNGE(int arr[], int n)
{
    int i = 0;
    struct stack s;
    s.top = -1;
    int element, next;

    push(&s, arr[0]);


    for (i=1; i<n; i++)
    {
        next = arr[i];

        if (isEmpty(&s) == false)
        {
            element = pop(&s);

            while (element < next)
            {
                printf("\n %d --> %d", element, next);
                if(isEmpty(&s) == true)
                   break;
                element = pop(&s);
            }
            if (element > next)
                push(&s, element);
        }
        push(&s, next);
    }

    while(isEmpty(&s) == false)
    {
        element = pop(&s);
        next = -1;
        printf("\n %d --> %d", element, next);
    }
}

int main()
{
    int arr[]= {11, 13, 21, 3};
    int n = sizeof(arr)/sizeof(arr[0]);
    printNGE(arr, n);
    getchar();
    return 0;
}
Time Complexity:O(n)
Simple Code in Java [ Easy to understand ]

public class Test {

    public static void upateArray(int[] a){
        Stack<Integer> stack = new Stack<Integer>();
        int len = a.length;
        int cur = 0;
        while(cur < len){
            while(!stack.isEmpty() && a[stack.peek()] < a[cur]){
                a[stack.pop()] = a[cur];
            }
            stack.push(cur);
            cur++;
        }
    }

    public static void main (String args[]){
        int a[] = {3,2,5,11,4,11,13,8,6,20,10};
        upateArray(a);
        for(int i : a)
            System.out.print(" "+i);
    }
}

Source:

http://stackoverflow.com/questions/5007941/next-larger-number-in-an-array 

Method 2:

Make an empty array called c[].
Start at the end of a[] and work backwards.
Do a binary search in c[] for the first value greater than a[i]. Put that into b[i], or a -1 if you can't find one.
Drop everything in c[] that is less than b[i].
Append a[i] to the beginning of c[].
c[] will always be sorted, allowing binary search.

---

For example, with the sample A={1,3,5,7,6,4,8}
Start at the end, A[i]=8, C={}
First iteration is a bit weird.
Binary search of C for the first value greater than 8 gives nothing, so B[i] = -1
You don't have to drop anything from C because it is empty, but you would have had to empty it anyway because of the -1.
Append A[i]=8 to the beginning of C, so C={8}
Now A[i]=4, C={8}
Binary search of C for the first value greater than 4 gives 8, so B[i]=8
Drop everything less than 8 from C, which still leaves C={8}
Append A[i]=4 to the beginning of C, so C={4,8}
Now A[i]=6, C={4,8}
Binary search of C for the first value greater than 6 gives 8, so B[i]=8
Drop everything less than 8 from C, which leaves C={8}
Append A[i]=6 to the beginning of C, so C={6,8}
Now A[i]=7, C={6,8}
Binary search of C for the first value greater than 7 gives 8, so B[i]=8
Drop everything less than 8 from C, which leaves C={8}
Append A[i]=7 to the beginning of C, so C={7,8}
Now A[i]=5, C={7,8}
Binary search of C for the first value greater than 5 gives 7, so B[i]=7
Drop everything less than 7 from C, which leaves C={7,8}
Append A[i]=5 to the beginning of C, so C={5,7,8}
Now A[i]=3, C={5,7,8}
Binary search of C for the first value greater than 3 gives 5, so B[i]=5
Drop everything less than 5 from C, which leaves C={5,7,8}
Append A[i]=3 to the beginning of C, so C={3,5,7,8}
Now A[i]=1, C={3,5,7,8}
Binary search of C for the first value greater than 1 gives 3, so B[i]=3
Done