Use an array to represent the stack. Push will add new integer to the array. Pop removes the last element in the array and increment will add val to the first k elements of the array.

This solution run in O(1) per push and pop and O(k) per increment.