Let $n$ be a positive integer. Each cell of an $n \times n$ table is coloured in one of $k$ colours where every colour is used at least once. Two different colours $A$ and $B$ are said to touch each other, if there exists a cell coloured in $A$ sharing a side with a cell coloured in $B$. The table is coloured in such a way that each colour touches at most $2$ other colours. What is the maximal value of $k$ in terms of $n$?
 
1. **Define the Problem and Graph Representation:**
   - Let \( n \) be a positive integer.
   - Consider an \( n \times n \) table where each cell is colored in one of \( k \) colors.
   - Each color is used at least once.
   - Two different colors \( A \) and \( B \) are said to touch each other if there exists a cell colored in \( A \) sharing a side with a cell colored in \( B \).
   - The table is colored such that each color touches at most 2 other colors.
   - We need to find the maximal value of \( k \) in terms of \( n \).

2. **Graph Construction:**
   - Consider a graph \( G \) where the vertices represent the \( k \) colors.
   - There is an edge between two vertices if the corresponding colors touch each other.
   - Since every color is used at least once and the table is connected, \( G \) is connected.
   - Each vertex in \( G \) has a degree of at most 2, implying \( G \) is either a path or a cycle.

3. **Case Analysis:**
   - **Case 1: \( G \) is a path.**
     - If \( G \) is a path, the maximum number of vertices (colors) is \( k \).
   - **Case 2: \( G \) is a cycle.**
     - If \( G \) is a cycle, the maximum number of vertices (colors) is \( k \).

4. **Bounding \( k \) for Odd \( n \):**
   - For odd \( n \), every cell in \( T \) can be reached from the center cell \(\left(\frac{n-1}{2}, \frac{n-1}{2}\right)\) in at most \( n-1 \) steps.
   - Therefore, \( G \) can have at most \( 2n-1 \) vertices.
   - Hence, \( k \leq 2n-1 \).

5. **Bounding \( k \) for Even \( n \):**
   - For even \( n \), every cell in \( T \) can be reached from the center cell \(\left(\frac{n}{2}, \frac{n}{2}\right)\) in at most \( n \) steps.
   - Therefore, \( G \) can have at most \( 2n \) vertices.
   - Hence, \( k \leq 2n \).

6. **Special Considerations for \( n \geq 4 \):**
   - For \( n \geq 4 \), consider the cells \((0,0)\), \((1,0)\), \((0,1)\), \((n,0)\), and \((0,n)\).
   - If \((0,0)\) has a unique color \( C \) with distance \( n \) in \( G \) from the color \( D \) of \(\left(\frac{n}{2}, \frac{n}{2}\right)\), it is the only cell with color \( C \).
   - If \((1,0)\) and \((0,1)\) have different colors, \( G \) must be a cycle of length \( 2n \), which contradicts the uniqueness of \( C \).
   - If \((1,0)\) and \((0,1)\) have the same color, the colors of \((n,0)\) and \((0,n)\) are reachable from \((1,0)\) and \((0,1)\) respectively in \( n-1 \) steps in \( G \) with a path not containing \( C \).
   - Thus, \( k \leq 2n-1 \) for even \( n \geq 4 \).

7. **Achieving the Bounds:**
   - These bounds can be achieved by coloring \((i,j)\) with the color \( i+j \) for \( n \neq 2 \).
   - For \( n = 2 \), color each cell with a unique color.

The final answer is \( \boxed{ k \leq 2n-1 } \) for odd \( n \) and \( k \leq 2n-1 \) for even \( n \geq 4 \). For \( n = 2 \), \( k = 4 \).