TSO-to-TSO linearizability, TSO-to-SC linearizability, and TSO linearizability are three typical variants of linearizability on the total store order (TSO) memory model. This study proposes k-bounded TSO-to-TSO linearizability and k-bounded TSO linearizability, and investigates the verification problems of k-bounded TSO-to-TSO linearizability, k-bounded TSO-to-SC linearizability, and k-bounded TSO linearizability that are bounded versions of the above variants of linearizability, defined on k-extended histories. Although the corresponding executions of k-extended histories contain a bounded number (less or equal than k) of call, return, flushCall and flushReturn actions, the verification problems of these three bounded versions of linearizability are non-trivial since the corresponding executions of k-extended histories may still contain an unbounded number of write actions and use store buffers with an unbounded capacity, which makes their operational semantics built upon infinite state transition systems. The k-bounded TSO-to-TSO linearizability problem, k-bounded TSO-to-SC linearizability problem, and k-bounded TSO linearizability problem between concurrent data structures and their sequential specifications are reduced into TSO-to-TSO linearizability problem between sets of k-extended histories, which provides a uniform framework for verifying the three bounded versions of linearizability on the TSO memory model. The key point of the proposed approach is to check if a concurrent data structure contains a specific k-extended history. It is proved that this problem is decidable by reducing it into the control state reachability problem of lossy channel machines, which is known decidable. This reduction essentially requires call and return actions to be transformed into write, flush or cas (compare-and-swap) actions. In the definition of TSO-to-TSO linearizability, a call or return action taken by a process changes the store buffer and the control state of the process at the same time. A specific write action is added immediately after each call or return action; thus, the influence on store buffers is mimicked by these specific write actions and their corresponding flush actions. To mimic the influence on control states, an observer process and bind specific cas actions of the observer process are introduced to each call or return actions. In this way, three bounded versions of linearizability are decidable on the TSO memory model are proved. Three bounded versions of linearizability on the TSO memory model are at level F_ω^ω are further proved in the fast-growing hierarchy of recursive functions. This is proved by stating that the reachability problem of single-channel basic lossy channel machines, which is known in such complexity class, can be reduced into the three bounded versions of linearizability problems on the TSO memory model, while the latter problem can also be reduced into the former problem.