I think that ahelwer's answer touches on some the ways that we think about the complexity of algorithms. However — given that we don't literally have "oracles" in the real world which we wish to query, you might wonder why we would worry about query complexity, or the idea of oracles at all. I will try to give some perspective on this, and in particular to describe how you might try to think of ways to construct a "Deutsch–Josza oracle" in a way that you don't feel as though you're cheating.

(As Norbert Schuch points out, for the Deutsch problem which is the elementary case of Deutsch–Josza, there's not much scope for insights, but I expect that your question about oracles applies more generally as well. That's what I'll speak to here.)

An intuition about oracles

The concept of an oracle is a way to allow ourselves to simplify how we talk about computational problems.

The original application of the concept of an oracle was to consider hypothetically what we could do if we could solve difficult problems, even impossible problems, without committing to how we could do it even in principle. But in computational complexity these days — particularly in quantum computation, e.g. in the cases of Deutsch–Josza, Bernstein–Vazirani, and other oracle problems — the situation is different: the oracle describes a function which is the basis of the problem. The fact that it is 'an oracle' is a way to structure how we describe the function which is at the centre of the problem: not that we must never contemplate how the function is computed, but that this information is simply not provided as part of the problem, and that we are not concerned with the time or other complexity associated with that function.

When we take this approach, we can actually obtain answers which are related to very difficult questions in computation. For instance, you may know that we do not know how to prove either P ≠ NP or P = NP, but that we can show that there are oracles A such that we can show that P^A ≠ NP^A. What the oracle A does here is not help a computer (more precisely, a deterministic Turing machine or a nondeterministic Turing machine) to solve a problem — it represents the problem which the computer must solve. The fact that we can show in some instances that P^A ≠ NP^A, doesn't mean that P is really different from NP: it just means that just using nondeterminism is really a significant resource for a model of computation to have — it allows you to solve some problems efficiently, and there is no way generically to simulate nondeterminism efficiently on a deterministic computer. So if you want to solve the problem related to what A computes, you absolutely would require some information about the structure of any function which could efficiently compute A.

This is one of the main things that oracles are about: they allow you to talk about ways that models of computation can or cannot solve problems, when you are provided with limited information about the problem.

Using oracle algorithms to solve non-oracle problems

The Deutsch–Josza algorithm, or the Bernstein–Vazirani algorithm, are in principles not algorithms which one performs for their own sake. (Well, not really — see the next Section.) They stand for ways that you can solve a problem. What problems do they solve? They allow you to discover certain features of a function you're interested in — whether it is constant/balanced, or what vector is associated in some scalar-valued linear function on vectors.

What functions do you perform them on? — You perform them on any function for which you are interested in the answer.

The description of these as oracle-based algorithms is beside the point. The oracle problems basically allow you to know that, with an ideal quantum computer, you can solve the problem even if you know extremely little about the function, provided that you can actually evaluate the function efficiently in practise. To actually evaluate such a function, of course you will need some description of how to do so, and so you have more information than in the oracle setting; but that doesn't prevent you from using the same algorithm.

What happens when you have more information than in the oracle setting, is that suddenly there are other ways that you might be able to solve the problem. Specifically, it might become possible to solve the problem efficiently classically. (This is the same observation as with P^A ≠ NP^A: it proves that there are problems which are in NP, which any efficient deterministic algorithm would at least require actual structural information to be able to solve — so that when you provide a description of an efficiently computable function rather than an 'oracle', it is possible that the problem will be in P.) It means that the quantum algorithm might not have the same advantage over classical algorithms at solving the particular problem you present — and in fact it may be that the classical approach is better (particularly with the devices we have at the moment).

In the end, just because you have a quantum algorithm to solve something, doesn't mean that it is necessarily the best way to solve something. This is certainly true of the Deutsch–Josza algorithm: even in the oracle setting, using randomness is nearly just as good, and it's much better given that we don't have large reliable quantum computers yet! But then again...

"Implementing" an oracle

The purpose of implementing the Deutsch–Josza algorithm is the same as implementing "Hello, World!" — not to solve a pressing unsolved problem, but to practise using a tool which you expect will be useful for doing other things.

To practise coding, you should feel absolutely relaxed and comfortable with the idea of implementing an oracle, and with the idea of the computer evaluating the oracle. In principle, this is the point of what you want to do. Even if you are using a classical emulator, in which the classical computer is actually evaluating all branches of the superposition and so explicitly finding the answer to a problem in order to pretend that it is a quantum computer acting in a slightly more roundabout way, so be it — you are practicing how to use a tool which may be useful for other things, and which one day won't be run on a classical computer.

So how should you go about implementing your oracle?

(i) If you are really committed to the idea that you are just getting practise, you don't have to pretend that you are doing anything magical. Come up with just any way to implement the oracle function, even if it is blatantly obvious to the casual observer whether the result is constant or balanced. You're just trying to practise realising an algorithm — don't worry that someone will accuse you of being an impostor, that you're pretending to cure cancer but are actually playing with Lego. You never were pretending to cure cancer, and you are playing with Lego by deliberate choice. Embrace that and just do it.

(ii) If you want to be sure that you aren't cheating somehow (nor the emulator, nor the eventual quantum computer), try to find a way to construct your oracle so that it is difficult to tell whether it is balanced or constant. This itself is not necessarily easy to do. It would be natural to try to do this by describing a function $f(x) = g(x,r)$ for some hidden parameter $r$, but coming up with a function $g(x,r)$ which is either constant or balanced for the evaluation of $x$, for any (or most?) values of $r$, and where it isn't obvious how to solve it classically, is non-trivial.

• For instance, you could let $g(x,r) = x \cdot r$ for $x,r \in \{0,1\}^n$, and consider a circuit which straightforwardly evaluates $g(x,r)$ on an auxiliary qubit. In this case, we would then know that $f(x)$ is either constant or balanced. However, the reason why we know this is because $f(x)$ is obviously balanced if and only if $r \ne 0$, and we could tell that easily from the circuit construction.

• It is conceivable that the above construction could be elaborated / obfuscated somewhat, to obtain a construction which is guaranteed to evaluate either a constant function or a balanced function, and where which of these two occurs is not obvious or even difficult — but I can't think of how, at the moment.

Bear in mind that this actually be very difficult to do — but if you can see a way to do it, it could be very worthwhile: Bravyi, Gossett, and Koening did something like this for the Bernstein–Vazirani problem, and it allowed them to show a small but unconditional separation between quantum and classical complexity, which was one of the more interesting things to occur in quantum complexity in the past several years.

TL;DR

• Don't sweat over the fact that you're 'evaluating' an oracle.

• If you sweat over anything, only worry that an actual description of the function might make it possible to solve the same problem easily without a quantum computer.

• If your motivation is only to get practise with quantum programming, don't even worry about that. Save your worrying for worthier problems, like global warming. In the meantime enjoy playing with Legos while you build to something more.