ON THE MAXIMUM QUEUE LENGTH WITH APPLICATIONS TO DATA STRUCTURES: A Simple But Yet Asymptotically Exact Approach

A dynamic data structure called queue is analyzed in this paper from the viewpoint of its maximum sizc. By dynamic queue we understand any data structure that is built during a sequence of insertions and deletions. The maximum size of such a structure is a fundamental quantity and is directly related to many problems of resource allocations. We assume that each element of the structure (we call it further a customer) stays for a random time in the system and then leaves it Furthermore, the interanival time of customers is a generally distributed random variable. Adopt-ing queueing theory language, we say the data structure is GIlGle queueing systems, where c (may be infinite) is the maximum number of items that can simultaneously leave the system (number of servers). We shall show that for stable staJionary queue the maximum queue length observed by the n-th arriving customer grows asymptotically in probability as loga; n, where a is a system constant